[백준/boj] 7576: 토마토 (Java) / BFS

문제

7576번: 토마토

 

 

 

토마토가 익어가는 과정을 그림으로 나타내 봤다. (최소 날짜 : 6)

풀이

import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N, M;
	static int[][] box;
	static Deque<Pos> deque;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static int emptyCnt = 0, zeroCnt = 0;
	static int day = -1;

	private static class Pos {
		int x;
		int y;

		Pos(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(br.readLine());
		M = stoi(st.nextToken());
		N = stoi(st.nextToken());
		box = new int[N][M];
		deque = new ArrayDeque<Pos>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				box[i][j] = stoi(st.nextToken());
				if (box[i][j] == 1)
					deque.add(new Pos(i, j));
				if (box[i][j] == 0)
					zeroCnt++;
			}
		}

		if (zeroCnt == 0) {
			System.out.println("0");
			return;
		}
		
		bfs();

		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(day);
	}

	private static void bfs() {
		while (!deque.isEmpty()) {
			day++;
			int limit = deque.size();
			for (int l = 0; l < limit; l++) {
				emptyCnt = 0;
				Pos tomato = deque.pollFirst();

				for (int i = 0; i < 4; i++) {
					int nx = tomato.x + dx[i];
					int ny = tomato.y + dy[i];
					if (!isRange(nx, ny)) {
						continue;
					}
					if (box[nx][ny] == 0) {
						box[nx][ny] = 1;
						deque.add(new Pos(nx, ny));
					}
				}
			}
		}
	}

	private static boolean isRange(int x, int y) {
		return x < 0 || x >= N || y < 0 || y >= M ? false : true;
	}

	private static int stoi(String input) {
		return Integer.parseInt(input);
	}
}

• 하루에 근접한 하나의 토마토만 익히기 때문에 bfs를 사용해야한다. 
• 익은 토마토가 2개 이상이라면 각자 다른 칸에서 하루 동안 동시에 토마토 익히기를 진행하기 때문에 새로 익은 토마토 칸 좌표를 deque에 넣고 다음 날에 그 deque의 size만큼 bfs를 실행한다.
  ==> limit = deque.size();
• 마지막에는 더 이상 익힐 토마토가 없어도 전날 익은 토마토들 때문에 while문이 한번 더 실행된다. 그렇기 때문에 day 를 -1로 초기화했다.