[Java] 백준 토마토

1. 문제분석

전형적인 BFS 문제 토마토를 보관하는 창고가 있고 익은 토마토는 사방면으로 안 익은 토마토에 영향을 준다.

 

먼저 익은 토마토의 좌표를 큐에 넣어준다. 익지 않은 토마토의 개수는 따로 저장해둔다.

(그래야 큐에서 빼고 사방면으로 옮기기 때문)

 

만약 안 익은 토마토가 존재하고, 큐에 데이터가 있으면 익은 토마토가 주변 토마토를 익게 해줄 수 있다.

큐에 뺀 토마토의 좌표에서 사방면으로 옮겨주고 안 익은 토마토에서 익은 토마토가 됐으면 그 토마토의 좌표를 큐에 넣는다.

 

이런식으로 반복하고 만약 안익은 토마토가 여전히 존재하면 -1, 다 익었다면 걸린 일 수를 출력해주자.

2. 구현

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        //가로
        int M = Integer.parseInt(input[0]);
        //세로
        int N = Integer.parseInt(input[1]);

        //사방면으로 움직이는 경우의 수
        int[] dx = new int[]{0, 0, -1, 1};
        int[] dy = new int[]{-1, 1, 0, 0};

        //토마토 저장 배열
        int[][] tomato = new int[N][M];

        //날짜
        int day = 0;

        //남은 토마토의 수
        int count = 0;
        
        Queue<int[]> queue = new LinkedList<>();

        //데이터 넣어주기
        for (int i = 0; i < N; i++) {
            String[] data = br.readLine().split(" ");
            for (int j = 0; j < M; j++) {
                int info = Integer.parseInt(data[j]);
                tomato[i][j] = info;
                if (info == 1) {
                    queue.add(new int[]{i, j});
                } else if (info == 0) {
                    count++;
                }
            }
        }
        
        //탐색 시작
        while (count > 0 && !queue.isEmpty()) {
            for (int i = queue.size(); i > 0; i--) {
                int[] arr = queue.poll();

                for (int range = 0; range < 4; range++) {
                    int moveX = arr[1] + dx[range];
                    int moveY = arr[0] + dy[range];
                    
                    //인덱스 오류 처리
                    if (moveX < 0 || moveY < 0 || moveY >= N || moveX >= M || tomato[moveY][moveX] != 0) continue;
                    
                    //익은 토마토로 변경
                    count--;
                    tomato[moveY][moveX] = 1;

                    queue.add(new int[]{moveY, moveX});
                }
            }
            day++;
        }
        System.out.println(count == 0 ? day : -1);
    }
}

사방면의 좌표를 미리 구현해두면 편하게 만들 수 있다.

또한 인덱스 오류 처리에서 이미 익은 토마토가 있을 수 있다. 그런 경우에도 빼주면 된다.

3. 마무리

BFS는 처음 풀어 보는데 앞서 풀어본 사방면을 좌표로 미리 구현하는 방법을 외워야겠다.

처음은 편법이라고 생각했지만 지금 보니 좋은 방법 같다.