https://softeer.ai/practice/info.do?idx=1&eid=411

문제

북위 65도. 스웨덴의 소도시 아르예플로그(Arjeplog)에 자리한 동계 테스트 센터. 겨울 내내 얼음 두께가 1M 내외로 유지되는 광할한 얼음 호수와 그냥 걷기조차 힘든 눈길을 무대로 현대자동차그룹 연구원들은 극한 환경 속에서 더 나은 차량 성능을 확보하기 위해 제동안정성, 주행안정성, ADAS 기능 등에 대한 다양한 평가를 숨가쁘게 이어가고 있다.

이 곳은 기온이 너무 추워서 아침에 출근해보면 테스트 차량들 위에 큰 눈얼음이 생겨 있다. 정상적인 테스트를 위해서는 커다란 얼음이 어느정도 녹고 난 뒤에 가능한데, 차량 마다 당일의 테스트 가능 시점을 알기 위한 예측 프로그램을 제작 중에 있다.

예측 프로그램은 N×M (5 ≤ N, M ≤ 100)의 격자 화면 위에 눈 얼음의 모양을 작은 정사각형들이 집합되어 있는 모양으로 변환하여 위 그림과 같이 표시해 준다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 얼음은 아침이 되면 기온이 상승하여 천천히 녹는다.

그런데 화면에서 나타난 얼음의 모양은 작은 정사각형 모양의 4변 중에서 적어도 2변 이상이 외부의 공기와 접촉했을 때 정확히 한 시간 만에 녹아 없어져 버린다. 따라서 위 그림의 모양과 같은 얼음(파란으로 표시된 부분)라면 C로 표시된 모든 얼음 격자는 한 시간 후에 사라진다.

위와 같이 얼음 내부에 있는 공간은 얼음 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므로 이 공간에 접촉한 얼음 격자는 녹지 않고 C로 표시된 얼음 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면, 아래 그림에서와 같이 C로 표시된 얼음 격자들이 사라지게 된다.

격자 화면의 맨 가장자리에는 얼음이 놓이지 않는 것으로 가정한다. 입력으로 주어진 얼음이 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성해보자.

제약조건

5 ≤ N, M ≤ 100

입력형식

첫째 줄에는 격자 화면의 크기를 나타내는 두 개의 정수 N, M이 주어진다. 그 다음 N개의 줄에는 격자 화면 위에 얼음이 있는 부분은 1로 표시되고, 얼음이 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

출력형식

출력으로는 주어진 얼음이 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

입출력 예제

• 입력예제1

8 9
0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0
0 0 0 1 1 0 1 1 0
0 0 1 1 1 1 1 1 0
0 0 1 1 1 1 1 0 0
0 0 1 1 0 1 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

• 출력예제1

4

Solution

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


public class Main
{
    static int[][] MATRIX = new int[101][101];
    static boolean[][] VISIT = new boolean[101][101];
    static int[][] MAP = new int[101][101];
    static int countOfIce = 0;
    static int[] dx = { 0, 0, 1, -1 };
    static int[] dy = { 1, -1, 0, 0 };

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                MATRIX[i][j] = Integer.parseInt(st.nextToken());
                if (MATRIX[i][j] == 1) {
                    countOfIce++;
                }
            }
        }

        bw.write(String.valueOf(BFS(N, M)));
        bw.flush();

    }

    public static void initSetup(int N, int M) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                MAP[i][j] = MATRIX[i][j];
                VISIT[i][j] = false;
            }
        }
    }

    public static void checkMap(int N, int M) {
        Queue<int[]> que = new LinkedList<>();
        VISIT[1][1] = true;
        que.add(new int[] { 1, 1 });

        while (!que.isEmpty()) {
            int X = que.peek()[0];
            int Y = que.peek()[1];
            que.poll();

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

                while (nx > 0 && nx <= N && ny > 0 && ny <= M && !VISIT[nx][ny] && MAP[nx][ny] == 0) {
                    VISIT[nx][ny] = true;
                    que.add(new int[] { nx, ny });
                }
            }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (!VISIT[i][j] && MAP[i][j] == 0) {
                    MAP[i][j] = -1;
                }
            }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (MAP[i][j] == 1) {
                    int count = 0;
                    for (int k = 0; k < 4; k++) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];

                        if (nx > 0 && nx <= N && ny > 0 && ny <= M && VISIT[nx][ny]) {
                            count++;
                        }
                    }
                    if (count >= 2) {
                        MATRIX[i][j] = 0;
                        countOfIce--;
                    }
                }
            }
        }
    }

    public static int BFS(int N, int M) {
        int result = 0;

        while (countOfIce != 0) {
            initSetup(N, M);
            checkMap(N, M);
            result++;
        }

        return result;
    }
}

한 번의 페이즈를 네가지 페이즈로 나눠서 문제를 해결했다.
1. 우선 얼음의 위치를 파악한다. 기존의 데이터는 MATRIX에 저장했고 MAP 배열을 따로 생성한다.
2. 바람이 부는 스팟을 미리 파악한다. VISIT 배열로 처리해둔다.
3. 이후 빈 공간이지만, 얼음 외부가 아닌 즉 VISIT 배열에 방문 기록이 없는 곳은 MAP에 따로 표기해둔다.
4. 이후 얼음이고 두 스팟 이상 바람을 맞는 곳을 찾는대로 MATRIX에서 삭제처리한다. 또한 총 얼음의 갯수도 갱신한다.