BJ7576 토마토

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

기본적인 BFS 문제이다.

익은 토마토를 리스트에 담아두고, BFS를 활용하여 토마토가 모두 익게 되는 일수를 출력하면 된다.

package day0225;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Tomato {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static int N, M, numofTomato = 0, numofTomato_M = 0;
	static int[][] map;
	static int[][] dir = {{0, 1},{0, -1},{1, 0},{-1,0}};
	public static class Tmt implements Comparable<Tmt> {
		int x, y, count;

		public Tmt(int x, int y, int count) {
			super();
			this.x = x;
			this.y = y;
			this.count = count;
		}

		@Override
		public int compareTo(Tmt o) {
			// TODO Auto-generated method stub
			return count - o.count;
		}
	}
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine(), " ");
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		PriorityQueue<Tmt> q = new PriorityQueue<>(); // 익은 토마토 리스트.
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 0 || map[i][j] == 1) {
					numofTomato++;
					if(map[i][j] == 1) {
						q.add(new Tmt(i, j, 0));
						numofTomato_M++; // 익은 토마토의 수.
					}
				}
			}
		}
		int max_count = 0;
		while(!q.isEmpty()) {
			Tmt cur = q.poll();
			if(cur.count > max_count) max_count = cur.count;
		
			for(int d = 0; d < 4; d++) {
				int nX = cur.x + dir[d][0];
				int nY = cur.y + dir[d][1];
				if(nX >= 0 && nX < N && nY >= 0 && nY < M && map[nX][nY] == 0) {
					map[nX][nY] = 1;
					numofTomato_M++;
					q.add(new Tmt(nX, nY, cur.count + 1));
				}	
			}
		}
		
		if(numofTomato == numofTomato_M) {
			bw.append(max_count +"");
		}else {
			bw.append("-1");
		}
		bw.flush();
	}
}