[백준/JAVA] BOJ 7576 - 토마토

👀 문제

7576번: 토마토 ✨ 골드 5

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

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

입력 예제

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

출력 예제

8

🔑 키포인트

그래프 이론 그래프 탐색 너비 우선 탐색

✍️ 코드

package jan_week5;

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 BOJ7576 {
	static int[][] tomatos;
	static Queue<int[]> queue;
	static int m, n;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());	
		
		m = Integer.parseInt(st.nextToken()); // 세로 칸 수 
		n = Integer.parseInt(st.nextToken()); // 가로 칸 수 
		
		tomatos = new int[n][m];
		queue = new LinkedList<>();
		int days = 0;
		
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < m; j++) {
				tomatos[i][j] = Integer.parseInt(st.nextToken());
                // 익은 토마토가 있으면 큐에 넣어 주기 
				if (tomatos[i][j] == 1) {
					queue.offer(new int[] {i, j});	
				}
			}
		}
		
		bfs();
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (tomatos[i][j] == 0) {
					System.out.println(-1);
					System.exit(0);
				}
				days = Math.max(tomatos[i][j], days);
			}
		}
		
		// 익은 토마토가 1이라 날짜 계산이 1부터 시작하므로 출력할 때는 -1해서 출력 
		System.out.println(days-1);
	}
	
	public static void bfs() {
		int[] dx = { -1, 1, 0, 0 };
		int[] dy = { 0, 0, -1, 1 };
		
		while (!queue.isEmpty()) {
			// 현재 위치 
			int[] t = queue.poll();
			
			// 상하좌우 탐색 
			for (int i = 0; i < 4; i++) {
				int nx = t[0] + dx[i];
				int ny = t[1] + dy[i];
				
				// 상자를 벗어나지 않고 아직 익지 않았다면 
				if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
					if (tomatos[nx][ny] == 0) {
						tomatos[nx][ny] = tomatos[t[0]][t[1]] + 1; // 현재 일수에 + 1
						queue.offer(new int[] {nx, ny});
					}
				}
			}
		}
		
	}

}