[BFS] 7576. 토마토

[BOJ] 7576. 토마토

📌 풀이 과정

시작 정점이 여러개인 BFS

1. 큐 초기화 (여러 시작점 설정)
   BFS 탐색 전, 익은 토마토(값이 1인 경우)의 위치를 모두 큐에 추가한다.

2. BFS를 통한 토마토 익히기
   큐에서 익은 토마토의 위치를 하나씩 꺼내고, 그 위치에서 상하좌우로 이동 가능한 곳을 탐색한다.

   이동한 위치에 익지 않은 토마토(값이 0인 경우)가 있다면, 해당 토마토를 익히고 값을 현재 위치의 값 +1으로 변경해 큐에 추가한다.

3. 큐가 빌 때까지 2번 과정을 반복하여 모든 토마토를 익힌다.

4. 결과 확인 및 최종 출력
   익지 않은 토마토가 남아 있다면 -1을 출력하고, 그렇지 않다면 토마토가 모두 익는 데 걸린 최대 날짜를 계산하여 출력한다.
   최종 출력은 계산된 최대 날짜에서 1을 뺀 값이다.

✨ 제출 코드

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 N, M;
	static int[][] tomato;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static Queue<int[]> Q = new LinkedList<>();

	public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken()); // 열
        M = Integer.parseInt(st.nextToken()); // 행
        tomato = new int[M][N];
        
        for(int i = 0; i < M; i++) {
        	st = new StringTokenizer(br.readLine());
        	for(int j = 0; j < N; j++) {
        		tomato[i][j] = Integer.parseInt(st.nextToken());
        		if(tomato[i][j] == 1) Q.add(new int[] {i, j}); // 익은 토마토만 큐에 넣기
        	}
        }
        
        bfs();
        
        int day = 0;
        for(int i = 0; i < M; i++) {
        	for(int j = 0; j < N; j++) {
        		if(tomato[i][j] == 0) { // 익지 않은 토마토가 존재하는 경우
        			System.out.println(-1);
        			return;
        		}
        		if(tomato[i][j] > day) {
        			day = tomato[i][j];
        		}
        	}
        }
        
        System.out.println(day-1);
	}
	
	
	static void bfs() {
		
		while(!Q.isEmpty()) {
			int[] tmp = Q.poll();
			
			int x = tmp[0];
			int y = tmp[1];
			for(int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if(nx >= 0 && nx < M && ny >= 0 && ny < N && tomato[nx][ny] == 0) {
					tomato[nx][ny] = tomato[x][y] + 1;
					Q.add(new int[] {nx, ny});
				}
			}
		}
	}

}