백준 7576 토마토

백준 7576 토마토

1. 문제 링크

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

7576번: 토마토

 

2. 문제 해결에 대한 아이디어

1. input으로 토마토 상자에 대한 정보를 받을 때, 익은 토마토의 위치를 큐에 담는다.

2. 큐가 빌 때까지 BFS를 통해 안 익은 토마토를 익게 한다.

3. 이 때 weight 배열에 토마토가 익은 날짜를 기록한다.

4. BFS가 끝나면 토마토 상자를 순회하며 안 익은 토마토가 있는지 확인하고, 최대가중치의 값을 구한다.

 

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

class Tomato {
	int y, x;

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

public class Main {

	static int[][] map;
	static int[][] weight;
	static int[] dirY = { 0, 0, -1, 1 };
	static int[] dirX = { 1, -1, 0, 0 };
	static Queue<Tomato> q = new LinkedList<>();
	static boolean printZero = true; // 다 익은 경우
	static int minDay = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int M, N;
		String[] mns = br.readLine().split(" ");
		M = Integer.parseInt(mns[0]);
		N = Integer.parseInt(mns[1]);

		map = new int[N][M];
		weight = new int[N][M];

		for (int i = 0; i < N; i++) {
			String[] line = br.readLine().split(" ");
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(line[j]);
				if (map[i][j] == 1) {
					q.add(new Tomato(i, j));
					weight[i][j] = 1;
				} else if (map[i][j] == 0) {
					printZero = false;
				}
			}
		}
		// 다 익은 경우
		if (printZero) {
			System.out.println(0);
			return;
		}

		while (!q.isEmpty()) {
			Tomato now = q.poll();
			int x = now.x;
			int y = now.y;
			for (int i = 0; i < 4; i++) {
				int xx = x + dirX[i];
				int yy = y + dirY[i];

				if (xx < 0 || yy < 0 || yy >= N || xx >= M || weight[yy][xx] != 0 || map[yy][xx] != 0)
					continue;

				weight[yy][xx] = weight[y][x] + 1;
				map[yy][xx] = 1;
				q.add(new Tomato(yy, xx));
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 0) { // 토마토가 다 안 익은 경우
					System.out.println(-1);
					return;
				} else {
					minDay = Math.max(weight[i][j], minDay);
				}
			}
		}

		System.out.println(minDay - 1); // 시작지점을 1로 했기 때문에 1 빼줌
	}

}

 

4. 채점 결과

 

5. 느낀 점

1. 처음에 틀리길래 왜 틀리나 하고 봤더니 처음부터 다 익은 경우를 고려했어야 했다.