[백준] 7576. 토마토 - 실버1

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

7576번: 토마토

 

문제 요약

정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

하루가 지나면 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 익지 않은 토마토가 익은 토마토의 영향을 받아 익게 된다. 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 출력하시오.

 

문제 해결 아이디어

bfs 탐색을 선택했다. 시작 전부터 익은 토마토인 좌표를 queue에 전부 넣었다. 좌표값과 함께 day값을 같이 queue 에 넣었다. while문을 돌며 day를 계속 갱신시켜 줬고, 어쨌든 마지막엔 최종 일수가 day에 저장되게 된다. 네 방향을 돌면서 아직 익지 않은 토마토가 있다면 1로 바꿔 주고 queue에 넣었다.

bfs 탐색을 마쳐도 -1로 가둬져(??) 있어 익지 못한 토마토가 있을 수 있기 때문에 bfs가 다 끝나고 0인 토마토가 있는지 확인해 주었다. 

 

완성된 코드

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_BOJ_7576_토마토_인주비 {

	/*
	 * 576ms
	 */

	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());
		int N = Integer.parseInt(st.nextToken());

		int[][] tomato = new int[N][M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				tomato[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		int day = 0;

		Queue<int[]> queue = new LinkedList<int[]>();

		// 토마토를 queue에 넣음
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (tomato[i][j] == 1) {
					queue.offer(new int[] { i, j, 0 });
				}
			}
		}

		int[] dr = { -1, 1, 0, 0 };
		int[] dc = { 0, 0, -1, 1 };

		while (!queue.isEmpty()) {
			int[] current = queue.poll();
			day = current[2];
			for (int p = 0; p < 4; p++) {
				int nr = current[0] + dr[p];
				int nc = current[1] + dc[p];
				if (nr >= 0 && nr < N && nc >= 0 && nc < M) {
					if (tomato[nr][nc] == 0) {
						queue.offer(new int[] { nr, nc, current[2] + 1 });
						tomato[nr][nc] = 1;
					}
				}
			}
		}

		// 안익은 토마토가 있는지 확인
		boolean flag = true;

		as: for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (tomato[i][j] == 0) {
						flag = false;
						break as;
					}
				}
			}

		if (flag)
			System.out.println(day);
		else
			System.out.println(-1);
	} // end of main
}