[JAVA] 백준 7576 토마토

 

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

 

문제분석

이 문제는 2차원 격자에서 익은 토마토가 하루마다 상하좌우로 인접한 안 익은 토마토를 익게 만드는 구조라서, 여러 시작점이 동시에 퍼지는 BFS 문제라고 보고 접근하였다.

입력 받을 때 처음부터 익어 있는 토마토 좌표들을 전부 모아서 한 번에 시작하도록 리스트에 담고 큐에 넣었고, 빈 칸(-1)은 애초에 방문 처리해서 전파 대상에서 제외한다. 전체 칸 수에서 빈 칸 수랑 처음 익은 토마토 수를 더해서 이미 다 익어 있는 경우는 바로 0 출력하게 처리했다. 그 다음에는 큐에 “같은 날에 익는 토마토 묶음” 단위로 넣어서 레벨 단위 BFS처럼 돌렸고, 각 좌표에서 상하좌우로 아직 방문 안 한 칸만 다음 날 리스트에 추가하면서 방문 처리하고 익은 토마토 개수도 증가시킨다.

하루치 전파가 끝날 때마다 time을 1씩 늘리고, BFS 끝난 뒤 전체 칸 수와 비교해서 전부 익었으면 걸린 날짜 출력, 아니면 -1 출력하도록 구현하여 해결했다.

 

* 메모리 측면에서 좋은 풀이는 아니라고 한다. 천재적으로 좋은 방법을 제안해줬는데, 바로 "큐의 사이즈만큼 for문을 돌기" 이다. 이렇게 한다면 시간을 count하면서도 BFS를 할 수 있다. 아직 갈 길이 멂을 느낀다..

코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // col
        int M = Integer.parseInt(st.nextToken()); // row
        // 원래는 N - M 이 row - col 이지만, 이 문제는 반대로 제공, 근데 반대로 해석해서 꼬였음.
        ArrayDeque<ArrayList<int[]>> q = new ArrayDeque<>(); // [[row,col],[row,col]...]인 arrayList가 저장됨. 시간 계산 때문에.
        boolean[][] isNot = new boolean[M][N]; // 안익은 토마토 위치
        boolean[][] isVisit = new boolean[M][N]; // 방문 여부

        int countNot = 0;
        ArrayList<int[]> first = new ArrayList<>();
        for (int row = 0; row < M; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 0; col < N; col++) {
                int tomato = Integer.parseInt(st.nextToken());
                if (tomato == 1) { // 익은 토마토인 경우
                    first.add(new int[] { row, col });
                    isVisit[row][col] = true;
                } else if (tomato == -1) { // 빈칸인 경우
                    isNot[row][col] = true;
                    isVisit[row][col] = true;
                    countNot += 1;
                } // 나머지는 모두 안익은 토마토이므로, 따로 저장하지 않음.
            }
        }
        q.offer(first); // 처음 저장

        int countTomato = first.size(); // 익은 토마토 count

        // 만일 모든 토마토가 익었다면 0 출력
        if (countNot + countTomato == N * M) {
            System.out.println(0);
            return;
        }

        int time = 0;
        while (q.size() != 0) {
            ArrayList<int[]> targetList = q.poll(); // 전파할 기준 토마토 리스트
            ArrayList<int[]> ar = new ArrayList<>(); // 다음 대상 토마토 리스트

            for (int i = 0; i < targetList.size(); i++) {
                int[] arr = targetList.get(i);
                int row = arr[0];
                int col = arr[1];
                // 범위를 안 벗어나면서, 방문 안한 토마토에만 접근
                if (row + 1 < M && !isVisit[row + 1][col]) {
                    ar.add(new int[] { row + 1, col });
                    isVisit[row + 1][col] = true;
                    countTomato += 1;
                }
                if (col + 1 < N && !isVisit[row][col + 1]) {
                    ar.add(new int[] { row, col + 1 });
                    isVisit[row][col + 1] = true;
                    countTomato += 1;
                }
                if (row - 1 >= 0 && !isVisit[row - 1][col]) {
                    ar.add(new int[] { row - 1, col });
                    isVisit[row - 1][col] = true;
                    countTomato += 1;
                }
                if (col - 1 >= 0 && !isVisit[row][col - 1]) {
                    ar.add(new int[] { row, col - 1 });
                    isVisit[row][col - 1] = true;
                    countTomato += 1;
                }
                isVisit[row][col] = true;
            }
            if (ar.size() != 0) {
                q.offer(ar);
                time += 1;
            }
        }
        if(countTomato + countNot == N * M) System.out.println(time);
        else System.out.println(-1);
    }

}