[JAVA] 백준 (골드5) 7576번 토마토

AIR·2024년 3월 21일

그래프 탐색 백준 골드 코딩테스트

코딩 테스트 문제 풀이

목록 보기

62/135

링크

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

문제 설명

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

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

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

입력 예제

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

출력 예제

풀이

최소 일수는 결국 최소 이동거리를 거리를 구하는 것이므로 BFS를 이용한다.
처음에 익은 토마토가 여러 개일 수 있으니 BFS전에 배열에서 1을 탐색하여 Queue에 삽입한다. 그리고 넣어둔 Queue로 BFS를 진행한다.

예제의 경우 BFS를 진행한 결과는 다음과 같다.

[1, -1, 7, 6, 5, 4]
[2, -1, 6, 5, 4, 3]
[3, 4, 5, 6, -1, 2]
[4, 5, 6, 7, -1, 1]

1을 기준으로 탐색을 진행할 때마다 인덱스를 갱신시켜 나가며 결국 최대값에서 1을 뺀 값이 걸린 최소 일수가 된다.

코드

//백준
public class Main {

    private static final int[] dr = {-1, 0, 1, 0};
    private static final int[] dc = {0, 1, 0, -1};
    private static int[][] tomatoes;
    private static int M;
    private static int N;
    private static Queue<int[]> queue = new LinkedList<>();

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());  //가로
        N = Integer.parseInt(st.nextToken());  //세로

        tomatoes = new int[N][M];

        //입력값 세팅
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                tomatoes[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //처음에 모든 토마토가 익어있는지 여부
        boolean prevContainsZero = Arrays.stream(tomatoes)
                .flatMapToInt(Arrays::stream)
                .anyMatch(num -> num == 0);

        //익은 토마토를 탐색하여 큐에 삽입
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (tomatoes[i][j] == 1) {
                    queue.add(new int[]{i, j});
                }
            }
        }

        //탐색
        bfs();

        //탐색 완료 후 안익은 토마토 존재 여부
        boolean containsZero = Arrays.stream(tomatoes)
                .flatMapToInt(Arrays::stream)
                .anyMatch(num -> num == 0);

        //마지막 날짜
        int result = Arrays.stream(tomatoes)
                .flatMapToInt(Arrays::stream)
                .max()
                .getAsInt();

        if (!prevContainsZero) {
            System.out.println(0);
        } else if (containsZero) {
            System.out.println(-1);
        } else {
            System.out.println(result - 1);
        }
    }

    private static void bfs() {

        while (!queue.isEmpty()) {
            int[] curPos = queue.poll();
            int curR = curPos[0];
            int curC = curPos[1];

            for (int i = 0; i < 4; i++) {
                int nextR = curR + dr[i];
                int nextC = curC + dc[i];

                if (nextR < 0 || nextC < 0 || nextR >= N || nextC >= M) {
                    continue;
                }

                //안익은 토마토일 경우 이전 좌표값을 더하여 갱신
                if (tomatoes[nextR][nextC] == 0) {
                    queue.add(new int[]{nextR, nextC});
                    tomatoes[nextR][nextC] = tomatoes[curR][curC] + 1;
                }
            }

        }
    }

}