백준 7576번 :: 토마토 (BFS)

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

7576번: 토마토

🎈 문제 풀이

- 박스를 순회하면서 익은 토마토(= 1)을 Queue(큐)에 담는다. 

- 익은 토마토(= 1)가 동시다발적으로 주위 안익은 토마토(= 0)에 영향을 줘야하기 때문에 일반 BFS방법처럼  일정한 시작점에서 시작할 수 없다. 

• Queue(큐)에 익은 토마토들을 먼저 넣고 하나씩 차례대로 빼서 익은 토마토로 바꾸고 최소 날짜를 더해준다.
• 예를 들어,  익은 토마토가 박스에 위치 A, 위치 B 2곳에 있다고 치자.  그럼 우선 A와 B를 큐에 넣는다.
• 먼저, A를 빼서 0이 있으면 1로 바꾸고 "최소 날짜"를 +1한 상태로 큐에 담는다. 
• 그리고 B도 마찬가지로 빼서 0이 있으면 1로 바꾸고 "최소 날짜"를 +1한 상태로 큐에 담는다.
• 결과적으로 A와 B의 "최소 날짜"는 같다. 동시다발적으로 움직인 것이다.

- 저장될 때부터 모든 토마토가 익어있는 상태면 0을 출력 => 상하좌우가 다 1이어서 최소날짜가 0이 됨. 

- 마지막으로 박스를 다시 순회하면서

• 토마토가 모두 익지 못한 상황(=0이 있는 경우)  : -1을 출력
• 모두 익어있는 상태면(=1 이거나 -1인 경우) : "최소 날짜" 출력

🎈 기억 할 것

정점 하나씩 순회하는 것이 아닌 동시다발적으로 정점들을 bfs로 돌려야 하는 경우 같이 출발하는 정점들을 큐에 담고 시작한다.

 

🎈 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Q7576_1 {
	static int M;
	static int N;
	static int[][] box;
	static int[][] moves = {{-1,0},{+1,0}, {0,-1}, {0, +1}};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		box = new int[M][N];

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

		System.out.println(bfs());

	}

	static int bfs() {
		Queue<Tomato> queue = new LinkedList<>();

		// 박스 순회하면서 익은 토마토들 먼저 담기
		for(int i=0; i<M; i++) {
			for(int j=0; j<N; j++) {
				if(box[i][j] == 1) queue.add(new Tomato(i, j, 0));
			}
		}

		int minDays = 0; //익기 위한 최소 날짜
		while(!queue.isEmpty()) {
			Tomato tomato = queue.poll();

			if(minDays < tomato.distance) minDays = tomato.distance;

			for(int[] move : moves) {
				int dx = tomato.x+move[0];
				int dy = tomato.y+move[1];

				if(dx < 0 || dx >= M || dy < 0 || dy >= N) continue;
				if(box[dx][dy] != 0) continue;

				box[dx][dy] = 1;
				queue.add(new Tomato(dx, dy, tomato.distance+1));
			}
		}

		if(isChecked()) return minDays;
		else return -1;
	}

	static boolean isChecked() {
		for(int i=0; i<M; i++) {
			for(int j=0; j<N; j++) {
				if(box[i][j] == 0) return false;
			}
		}
		return true;
	}

	static class Tomato {
		int x;
		int y;
		int distance;

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