[백준] 7576 : 토마토 JAVA 풀이

 

익은 토마토의 주변을 점진적으로 탐색해야 하기 때문에 bfs를 사용했다.

 

 

 

import java.io.*;
import java.util.*;
public class Main {
	
	static int[] dx = {0,0,-1,1};
	static int[] dy = {1,-1,0,0};
	static int[][] box;
	static int N;
	static int M;
	static Queue<Tomato> queue = new LinkedList<>();
	
	static class Tomato{
		int x;
		int y;
		
		Tomato(int x, int y){
			this.x=x;
			this.y=y;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		M = Integer.parseInt(st.nextToken()); // 가로
		N = Integer.parseInt(st.nextToken()); // 세로
		
		box = new int[N][M];
        
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine()," ");
			for(int j=0;j<M;j++) {
				box[i][j] = Integer.parseInt(st.nextToken());
				
                // 익은 토마토라면 큐에 추가
				if(box[i][j]==1) {
					queue.add(new Tomato(i,j));
				}
			}
		}
		System.out.println(bfs());
	}
	
	public static int bfs() {
		while(!queue.isEmpty()) {
			Tomato t = queue.poll();
			
			int x= t.x;
			int y=t.y;
			
			for(int i=0;i<4;i++) {
				int nx = x+dx[i];
				int ny = y+dy[i];
				
				if(nx>=0&&ny>=0&&nx<N&&ny<M) {
					if(box[nx][ny]==0) {
						queue.add(new Tomato(nx,ny));
						box[nx][ny] = box[x][y]+1;
					}
				}
			}
		}
		
		int result = -999;
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
            	// 안 익은 토마토가 있다면 -1 반환
				if(box[i][j]==0) return -1;
				
                // 그렇지 않으면 result값 업데이트
				result = Math.max(result, box[i][j]);
			}
		}
		
        // 토마토가 다 익는 데 걸리는 일수가 1일 == 처음부터 다 익은 토마토뿐이었다는 뜻
		if(result==1) return 0;
		else return result-1; // 익는 데 걸리는 최소일수 반환
	}
}