백준 - 7576번(토마토)

문제 출처: https://www.acmicpc.net/problem/7576

문제

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

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

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    private static int[][] directions = {
    		{ -1, 0 },	// 상
    		{ 1, 0 },	// 하
    		{ 0, -1 },	// 좌
    		{ 0, 1 },	// 우
    };
    
    private static Queue<int[]> tomatoList = new ArrayDeque<>(); // 인덱스 0: 행, 인덱스 1: 열
    private static int[][] tomatoes; // 토마토 정보를 저장하기 위한 배열

	private static int countOne, countZero, countMinusOne; // 1, 0, -1 각각 카운트
    private static int result; // 정답용

	public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        
        int M = Integer.parseInt(tokenizer.nextToken()); // 상자 가로 길이
        int N = Integer.parseInt(tokenizer.nextToken()); // 상자 세로 길이
        
        tomatoes = new int[N][M];
        for (int i = 0; i < N; i++) {
			tokenizer = new StringTokenizer(reader.readLine());
			for (int j = 0; j < M; j++) {
				tomatoes[i][j] = Integer.parseInt(tokenizer.nextToken());
				
				if (tomatoes[i][j] == 1) {
					tomatoList.offer(new int[] { i, j }); // 익은 토마토 위치 삽입
					countOne++;
				}
				else if (tomatoes[i][j] == 0) countZero++;
				else countMinusOne++;
			}
		}
        
        // 모든 토마토가 다 익었거나, 익은 토마토와  빈 상자로만 구성된 경우 바로 리턴
        if (countOne == N * M || countOne + countMinusOne == N * M) {
        	System.out.println(0);
        	return;
        }
        
        while (!tomatoList.isEmpty()) {
        	int size = tomatoList.size();
			boolean flag = false;
        	while (size-- > 0) {
				if (bfs(tomatoList.poll(), N, M)) flag = true;
			}

        	if (flag) result++;
		}

        // 모두 익지 못하는 상황
        if (countOne + countMinusOne != N * M) {
			System.out.println(-1);
			return;
		}

		System.out.println(result);
    }
    
    private static boolean bfs(int[] code, int N, int M) {
    	int y = code[0];
    	int x = code[1];

    	boolean flag = false;

		for (int i = 0; i < 4; i++) {
			int dy = y + directions[i][0];
			int dx = x + directions[i][1];

			// 유효한 좌표값이고
			if (dy >= 0 && dy < N && dx >= 0 && dx < M) {
				// 익지 않은 토마토일 경우
				if (tomatoes[dy][dx] == 0) {
					tomatoes[dy][dx] = 1; // 토마토가 익음
					countOne++;
					flag = true;
					tomatoList.add(new int[] { dy, dx });
				}
			}
		}

		return flag;
    }

}

• BFS를 이용하여 풀었다.
• 처음에 입력값을 받을 때 각각의 상태에 해당하는 변수를 카운팅하여 익은 토마토와 익지 않은 토마토, 빈 상자의 개수를 파악한다.
• 익은 토마토의 경우, tomatoList를 만들어 좌표값과 함께 추가한다. 좌표값은 2차원 배열로 처리하였다.
• tomatoList에서 익은 토마토 정보를 하나씩 빼내어 처리하는데, 이 리스트가 비게 되면 탐색을 종료한다.
• 탐색 전 현재 큐의 사이즈를 구한다. 이 사이즈가 현재 레벨에서 탐색할 개수이다.
• 각 레벨별로 탐색을 하는데, 이때 안익은 토마토에 영향을 미친 토마토가 단 하나라도 있다면 날짜를 증가시키고, 그렇지 않으면 증가시키지 않는다.
• BFS를 수행하며 새로 익은 토마토가 생기면 큐 추가한다.
• 만약, 모든 익은 토마토에 대한 처리를 마쳤는데 익은 토마토의 수와 빈 상자 수의 합이 전체 상자 개수와 같지 않으면 이는 도달할 수 없는 토마토가 있다는 뜻이므로 -1을 출력한다.
• 애시당초 모든 토마토가 익었거나 익은 토마토와 빈 상자로만 구성된 입력이 들어오면 바로 0을 출력하고 종료한다.