백준 7576 토마토 (BFS)

1. 문제

https://www.acmicpc.net/problem/7576

 

2. 설명

BFS 최단경로랑 비슷하게 풀면 된다.

다 익는 최소 날짜를 구하는 거라 조금 다르긴 한데 엇비슷..

다른 분들은 시간도 메모리도 적게드는데 어떻게 한거지ㅠ

 

3. 코드

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[] goX = {-1, 1, 0, 0};
	static int[] goY = {0, 0, -1, 1};
	
	static void bfs(int N, int M, int[][] box) {
		Queue<int[]> q = new LinkedList<int[]>();
		int[][] cnt = new int[N][M];
		int max = 0;
		
		// 토마토가 익은 부분을 큐에 넣음
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(box[i][j]==1) {
					cnt[i][j] = 0;
					q.add(new int[] {i,j});
				}
			}
		}
		
		while(!q.isEmpty()) {
			int curX = q.peek()[0];
			int curY = q.peek()[1];
			q.poll();
			
			for(int i=0; i<4; i++) {
				int nx = curX + goX[i];
				int ny = curY + goY[i];
				
				if(0<=nx && nx<N && 0<=ny && ny<M) {
					if(box[nx][ny]==0) {
						box[nx][ny] = 1;
						q.add(new int[] {nx,ny});
						cnt[nx][ny] = cnt[curX][curY] + 1; // 날짜 +1
						max = Math.max(max, cnt[nx][ny]); // 최소날짜
					}
				}
			}
		}
		
		// 출력
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(box[i][j]==0) {
					System.out.println(-1);
					return;
				}
			}
		}
		System.out.println(max);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(st.nextToken()); // M:가로
		int N = Integer.parseInt(st.nextToken()); // N:세로
		
		int[][] 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());
			}
		}
		
		bfs(N,M,box);
	}
}