[JAVA] 백준 7576번 : 토마토 (BFS)

www.acmicpc.net/problem/7576

7576번: 토마토

문제

해결 방안

BFS를 기본으로하여 구현하였다. 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// 토마토
// 며칠이 지나면 토마토가 다 익게되는지 최소 일수
public class Main {

	static int M; // 가로 (2~1000)
	static int N; // 세로
	static int[][] map; // NxM (1(익음),0(안익음),-1(없음))
	static boolean[][] visited;
	static Queue<int[]> loc = new LinkedList<int[]>(); // 익은 것들 위치
	static int[] dx = {0, 1, 0, -1}; // 북, 동, 남, 서
	static int[] dy = {-1, 0, 1, 0}; // 북, 동, 남, 서
	static int totalTomatoCnt = 0; // 총 토마토 갯수
	static int tomatoCnt = 0; // 익은 토마토 cnt
	static int result = 0; // 토마토가 모두 익는 최소 날짜
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		M = Integer.parseInt(str.split(" ")[0]);
		N = Integer.parseInt(str.split(" ")[1]);
		
		map = new int[N][M];
		visited = new boolean[N][M];
		
		StringTokenizer st;
		for(int i=0; i<N; i++) {
			str = br.readLine();
			st = new StringTokenizer(str);
			
			for(int j=0; j<M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				// 토마토 갯수
				if(map[i][j]==1 || map[i][j] == 0) {
					
					totalTomatoCnt++;
					// 익은 토마토를 
					if(map[i][j]==1) {
						tomatoCnt++;						
						loc.offer(new int[]{i,j});
						visited[i][j] = true;
					}
					
				}
			}
		}
		
		bfs();
		
		System.out.println(result);
	}
	
	static void bfs() {
		if(tomatoCnt == totalTomatoCnt) {
			return;
		}
		
		Queue<int[]> depthLoc = new LinkedList<>();
		int[] current = new int[2];
		int nx, ny;
		
		while(!loc.isEmpty()) {
			if(tomatoCnt == totalTomatoCnt) {
				break;
			}
			
			while(!loc.isEmpty()) {
				current = loc.poll();
				depthLoc.offer(current);
			}
			
			while(!depthLoc.isEmpty()) {
				current = depthLoc.poll();
				
				for(int i=0; i<4; i++) {
					nx = current[1] + dx[i];
					ny = current[0] + dy[i];
					if(nx<0 || nx>=M || ny<0 || ny>=N) {
						continue;
					}
					else {
						if(!visited[ny][nx] && map[ny][nx]==0) {
							visited[ny][nx] = true;
							map[ny][nx]=1;
							loc.offer(new int[] {ny, nx});
							tomatoCnt++;
						}
					}
				}
				
			}
			result++;
			
		}
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j]==0) {
					result = -1;
				}
			}
		}
		
	}

}