[백준] 7576 토마토 자바 BFS 문제 풀이 및 정답

 

문제 요약)

- 익은 토마토가 4방향의 토마토를 익히는데 1일씩 걸림

- 토마토가 없는 구간은 빈 구간

- 모든 토마토를 익히는데 걸리는 최소 일 수 구하기

 

주의점)

- 보통 세로, 가로 순서로 주는데 해당 문제는 가로, 세로 순서로 주어짐

- 출발점이 한 곳이 아닌 여러 곳일수도 있다.

- 토마토가 없는 곳으로 둘러싸여 있으면 평생 안익는 토마토 존재 가능

 

풀이)

BFS로 접근했을 때 가장 직관적인 방법은 토마토 있고 없고 표기할 맵, 방문배열, 거리를 표기할 거리배열 등 총 3개를 사용하면 가장 직관적으로 풀 수 있습니다. 하지만 거리 배열을 잘 활용하면 방문배의 역할도 같이 할 수 있기 때문에 메모리 낭비를 줄여나갈 수 있습니다. 배열을 어떻게 쓰든 시작점을 q에 차곡차곡 넣어놓은 뒤 4방향 탐색을 해나가면서 풀어나갈 수 있습니다.

 

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


public class Tomato7576_3_blog {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int m,n;
    static int[][] map, days;
    static int answer = 0, remainTomato = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");

        m = Integer.parseInt(s[0]); // 가로
        n = Integer.parseInt(s[1]); // 세로

        map = new int[n][m];
        days = new int[n][m];

        Queue<int[]> q = new LinkedList<>();

        // 입력 채워주기 및 익은 토마토면 q에 넣기
        for (int i=0; i<n; i++) {
            s = br.readLine().split(" ");
            for (int j=0; j<s.length; j++) {
                map[i][j] = Integer.parseInt(s[j]);
                if (map[i][j] == 0) {
                    remainTomato++;
                } else if (map[i][j] == 1) {
                    q.offer(new int[] {i, j});
                    days[i][j] = 0;
                }
            }
        }

        BFS(q);

        if (remainTomato > 0) answer = -1;
        System.out.println(answer);

    }

    static void BFS(Queue<int[]> q) {
        while (!q.isEmpty()) {
            int[] current = q.poll();

            for (int k=0; k<4; k++) {
                // 4방향 탐색
                int nx = current[0] + dx[k];
                int ny = current[1] + dy[k];
                // out of index 방지
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                    continue;
                }
                // 토마토가 이미 있거나, 아예 없거나, 방문을 이미 했던 거면 패스
                if (map[nx][ny] != 0 || days[nx][ny] > 0) {
                    continue;
                }
                // 방문안했고 안 익은 토마토인 경우니까 q에 넣고 날짜 표기해주기, 채웠다는 표시로 remainTomato 하나씩 빼주기
                q.offer(new int[] {nx, ny});
                days[nx][ny] = days[current[0]][current[1]] + 1;
                answer = Math.max(answer, days[nx][ny]);
                remainTomato--;
            }
        }
    }
}