🔍 문제

---

💻 제출

📌 입력

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다.

세로와 가로의 길이는 최대 100이다.

판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.

치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.

📌 출력

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

---

📝 코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
    static int N, M;
    static int[][] map;
    static int cheeseCnt = 0;
    static int[] dx = {0, 1, 0, -1}; //동 남 서 북
    static int[] dy = {1, 0, -1, 0}; //동 남 서 북
    static ArrayList<Integer> cTransferTime = new ArrayList<>(); //치즈 변화 시간

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];

        for (int i = 0; i < N; i++) {
            StringTokenizer stD = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                int data = Integer.parseInt(stD.nextToken());

                if (data == 1) { //치즈 개수 계산
                    cheeseCnt++;
                }

                map[i][j] = data;
            }
        }

        while (cheeseCnt != 0) {
            //맵에 치즈가 존재 하지 않을 때 까지 반복

            cTransferTime.add(cheeseCnt); //치즈 개수 저장 , 0번 index 는 0시간 , 1번은 1시간...
            bfs();
        }

        int time = cTransferTime.size();

        bw.write(time + "\n");
        bw.write(cTransferTime.get(time - 1) + "\n");
        bw.flush();
        bw.close();
        br.close();
    }


    static void bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0, 0});
        boolean[][] visited = new boolean[N][M];
        visited[0][0] = true;

        while (!q.isEmpty()) {
            int[] poll = q.poll();
            int cx = poll[0]; //poll x좌표
            int cy = poll[1]; //poll y좌표

            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];

                if (0 <= nx && nx < N && 0 <= ny && ny < M) {
                    if (visited[nx][ny] == false) {
                        //방문 하지 않은 영역
                        visited[nx][ny] = true;

                        if (map[nx][ny] == 1) {
                            //cheese 영역 이라면
                            map[nx][ny] = 0; //빈 공간으로 변환
                            cheeseCnt--;
                        } else {
                            q.offer(new int[]{nx, ny});
                        }
                    }
                }
            }
        }
    }

}

---

📗 정리

cTransferTime 배열을 통해서 시간 경과 후 치즈 변화 량을 체크 해줬다.

문제에서 치즈가 전부 없어지기 1시간 전의 치즈를 요구 하는 바람에 고민하다가 그냥 ArrayList로 저장하고 마지막 저장 값이 1시간 전 치즈 라고 판단 하여 사용했다.

가장자리는 치즈가 발생하지 않는 영역 이므로 (0,0)좌표 에서 BFS를 탐색 해줬으며 1시간 경과 할 때 마다 모든 가장 자리부터 탐색 해야 하기 때문에 시간 초과의 우려가 컷다.

시간 초과 없이 정상적으로 제출이 가능 한 이유는 겉에서 부터 치즈를 줄여 가면서 탐색하기에 배열 전체 탐색이 아니라서 그런거 같기도 하다.

문제 에서는 치즈 내부에 공기가 없는 것을 전제로 진행 했지만 만약 내부에서도 치즈가 줄어간다면 다양한 변수가 발생 할 것 같았다.