[백준 P23634] 미안하다 이거 보여주려고 어그로 끌었다 Java

P23634 미안하다 이거 보여주려고 어그로 끌었다

23634번: 미안하다 이거 보여주려고 어그로 끌었다

 

문제

난 나뭇잎 마을의 초대 호카게인 센쥬 하시라마의 동생, 센쥬 토비라마라고 한다. 지금 우리 마을은 크나큰 위기에 빠져있다. 우리와 끊이지 않는 악연을 지닌 우치하 가문의 수장 우치하 마다라가 구미를 끌고 마을을 습격했기 때문이지. 형은 호카게로서 마다라와 전투를 벌이고 있고 마을 주민들에게 피해가 갈까 봐 제대로 전투하지 못하고 있어. 지금 놈의 화둔이 마을로 넘어오지 못하게 우리 형의 목둔이 막아주고 있으니 나무가 크게 불타기 전에 미리 주민들을 대피시켜야 해. 나뭇잎 마을을 지키려면 네 도움이 필요해.

현재 상황은 마을 뒷산에서 전투가 일어나고 있고, 형의 나무가 불길을 막아서고 있어. 지도를 통해 살펴보면 마을 뒷산은 N×M의 직사각형의 격자에 해당하는 형태임을 알 수 있지. 아, 지도의 밖은 돌로 둘러싸여 있어 불이 퍼질 수 없으니 걱정하지 마.

불은 상하좌우로 인접한 나무를 통해서만 퍼져나갈 수 있고, 어떤 날에서 그다음 날로 넘어갈 때, 각 불은 동시에 퍼지게 돼. 불과 접촉한 나무는 다음 날 전부 불에 타서 불길이 되어버려. 하지만, 돌이 있는 지역은 불이 붙지 않아.

너도 알다시피 대피에는 시간이 굉장히 중요해. 우리는 주민들이 안전히 대피할 수 있도록 만날 수 있는 모든 불이 합쳐지는 최소 시간과 그때의 불의 크기를 구해야만 해. 불이 돌에 막혀 모든 불이 하나로 합쳐지지 않을 수도 있는데, 그럴 땐 합쳐질 수 있는 모든 불이 합쳐지는 최소 시간과 그때의 불의 크기의 합을 구하면 돼.

불이 합쳐진다는 것은 불이 다른 불과 상하좌우로 인접하게 되는 것을 뜻하고, 불의 크기는 불이 붙은 칸의 개수를 말해.

부탁해! 어서! 문제를 해결해서 우리 마을과 형에게 도움을 줘!

 

입력값

첫 번째 줄에 지도의 크기를 나타내는 정수 N, M이 주어진다. (1≤N,M≤2,000)

두 번째 줄부터 N+1번째 줄까지 0,1,2로 이루어진 첫날 지도가 표시된다. (불 = 0, 나무 = 1, 돌 = 2)

5 11
00111110100
01111110111
01111111110
11110011111
11000000111

5 6
011112
201120
022211
111101
111111

3 3
111
101
111

 

출력값

만날 수 있는 모든 불이 만나는 최소 시간과 그때의 불의 크기의 합을 출력한다. 첫날은 0일차이다. 즉, 처음부터 합칠 수 있는 모든 불이 합쳐져 있다면 최소 시간은 0이다.

만약 퍼질 불이 없다면, “0 0"을 출력한다.

2 53

2 20

0 1

 

알고리즘

말 그대로 제목에 어그로가 끌려서 문제를 풀게되었다.

진짜 진짜 진짜 너무 난해하고 어려웠다. 개인적으로 백조의 호수와 비슷한 문제라고 생각해서 풀었지만, 비슷하면서도 살짝 다른 내용이 있어 자료구조를 설계하기 어려웠다… 아래는 백조의 호수.. 이 문제를 먼저 풀어보는 것을 추천한다.

[백준 P3197] 백조의 호수 Java

 

알고리즘을 설명하기에 앞서 결과적으로 이 글을 올리는 시점에 Java로 이 문제를 풀이한 유일한 사람이 되었다…! (뭔가 뿌듯한?)

 

숏코딩도 1등이다…! (당연히 1명 중에서 1등이겠지만)

 

물론 이렇게 되기 전 까지 꽤 많은 시도를 거쳐왔다. 진짜 시간초과와 메모리초과를 마주칠 때 마다 최적화를 끊임없이 생각했던 것 같다.

(사실 저 87%에서 메모리 초과가 났을 땐 울고 싶었ㄷ…)

 

아무튼 알고리즘을 간략하게 설명해보겠다. 이 문제는 퍼져있는 불이 합쳐질 수 있는지를 체크해야 한다. 이 부분은 Union Find 알고리즘을 활용할 것이다. 마을의 전 부분을 순차적으로 탐색하면서 불(0)을 만나면, bfs 탐색을 하여 인접한 불들을 같은 집합에 속한 것으로 처리한다. groupIdx라는 배열을 이용했으며, groupIdx에는 따라서 4방(상 하 좌 우)로 인접한 불들은 같은 그룹으로 묶인다. 아래의 그림과 같다. (예제 입력 2번을 기준으로 설명한다.)

 

동시에 그 불이 바로 다음에 태우게 될 나무를 trees 큐에 저장한다. 이후에 이 큐에서 좌표를 하나씩 꺼내면서 불에 타는 것을 처리하고 다음에 탈 나무를 큐에 저장할 것이다. 초기의 큐의 상황은 다음과 같다.

 

초기 세팅을 마쳤다면 크게 세 가지 경우를 고려해야 한다.

1. 처음부터 불이 1개로 합쳐져 있는 경우
2. 불이 1개로 합쳐져 있지 않지만, 미래에 모든 불이 합쳐질 수 있는 경우
3. 불이 1개로 합쳐져 있지 않고, 미래에 모든 불이 합쳐질 수 없는 경우

 

처음부터 불이 1개로 합쳐져 있는 경우는 쉽다. 문제에 조건에 따라 처음부터 합칠 수 있는 모든 불이 합쳐져 있다면 최소 시간이 0이므로 “0 {현 상태에 존재하는 모든 불의 수}” 를 출력하면 된다. 참고로 groupMax는 위의 과정을 통해 인접한 불들을 그룹화 하는 과정에서 얻게 되는 “몇 개의 불 그룹이 도시에 존재하는지”의 값이다. 따라서 groupMax가 0 또는 1이라면, 도시에 불이 없거나 이미 모든 불이 합쳐져 있다고 생각할 수 있다.

if (groupMax <= 1) {
    System.out.println("0 " + countFire());
}

 

이 문제의 하이라이트이다. 2와 3 상황을 이해해보자. 2번 예제 입력을 살펴보자.

5 6
011112
201120
022211
111101
111111

 

이 입력의 경우에, 총 5개의 그룹이 나온다. 하지만 중간에 돌(2)로 둘러쌓여 있기에, 위쪽 불 그룹과 아래쪽 불 그룹으로 나뉘게 된다. 불은 돌을 넘을 수 없기 때문에, 위의 불 그룹과 아래 불 그룹이 합쳐지는 순간 답을 출력해야 한다. 처음에는 이를 매 루프마다 탐색하면서 연결될 수 있는 불들이 연결되었는지 확인하려 했다. 그러나 당연히 시간초과가 발생했고 다른 방법을 찾아야 했다. 즉, 미래에 연결될 수 있는 불 그룹이 모두 합쳐지는 그 순간을 찾아야 했다.

결국 해결한 방법은 한 번의 Union Find를 초기에 추가로 진행하는 것이다.

public static void unionFire() {
    Queue<int[]> q = new ArrayDeque<>();
    boolean[][] visited = new boolean[N][M];
    boolean[] searched = new boolean[groupMax + 1];

    parent = new int[groupMax + 1];
    grouped = new int[groupMax + 1];

    for (int i = 1; i <= groupMax; i++) {
        parent[i] = i;
        grouped[i] = i;
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!visited[i][j] && graph[i][j] == 0 && !searched[groupIdx[i][j]]) {
                int groupFlag = groupIdx[i][j];

                q.add(new int[] {i, j});
                visited[i][j] = true;
                searched[groupFlag] = true;

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

                    for (int d = 0; d < 4; d++) {
                        int newR = curR + dr[d];
                        int newC = curC + dc[d];

                        if (0 <= newR && newR < N && 0 <= newC && newC < M) {
                            if (!visited[newR][newC] && graph[newR][newC] != 2) {
                                visited[newR][newC] = true;

                                if (graph[newR][newC] == 0 && groupIdx[newR][newC] != groupFlag && !searched[groupIdx[newR][newC]]) {
                                    searched[groupIdx[newR][newC]] = true;
                                    union(groupFlag, groupIdx[newR][newC], grouped);
                                }

                                q.add(new int[] {newR, newC});
                            }
                        }
                    }
                }
            }
        }
    }
}

 

일반적인 Union Find를 변형하여 두 개의 대표값 배열을 선언했다. parent에는 특정 시점에 불 그룹들이 연결되어 있는지를 저장할 것이다. grouped에는 미래에 서로 연결될 수 있는 불 그룹들을 처음에 탐색하여 저장할 것이다. parent배열은 루프를 돌면서 인접한 곳에 다른 불 그룹을 만나면 Union 연산을 진행하여 그 순간 두 불 그룹이 만났다는 것을 표현한다. 이와는 반대로 grouped배열은 맨 처음에 모든 경우의 수를 탐색하기 위해 돌이 있지 않은 부분을 순차적으로 탐색하면서 다른 불 그룹을 만날 수 있다면 미리 Union 연산을 진행하여 두 불이 언젠가는 만날 수 있음을 저장했다. 초기에 이 부분을 수행한 이후 두 배열의 상태는 다음과 같다. (예제 입력 2를 기준으로 실행했다.)

 

이 과정을 거치면 현재 parent 배열 상태처럼 아무 불 그룹이 연결되어 있지 않음을 저장할 수 있고, 마지막에는 1번과 3번 두 개의 불 그룹으로 나누어진다는 것을 저장할 수 있다.

 

이후에는 모든 불이 합쳐질 때 까지 반복문을 진행하면 된다. 반복문을 진행하면서 불을 인접한 곳으로 이동해야 한다. 이동하면서 groupIdx 를 수정하며 새롭게 생기는 불도 인접한 불의 idx를 가지도록 지정하고, 인접한 곳에 나무(1)이 존재한다면 새롭게 큐에 넣어 다음 시점에 불에 탈 수 있도록 해야한다. 이 부분에서 나무가 타버려서 이전에 합쳐지지 않았던 새로운 불 그룹을 만난다면 Union 연산을 통해 parent 배열을 업데이트 해준다. 아래는 1번의 반복문을 실행한 이후에 graph(도시의 현 상황), groupIdx(불 그룹 상황), parent(불 그룹이 만난 상태), trees(새롭게 추가된 나무)의 모습이다. 1, 2번째 불 그룹과 3, 5 번째 불 그룹이 서로 만나 parent 배열이 바뀐 것을 볼 수 있다.

 

마지막으로 반복문을 멈추는 조건인 모든 불이 서로 연결되었는지 판단하는 부분이다. 이 부분은 모든 그룹을 순회하면서 parent(현재 불 그룹) 과 grouped(그 불이 마지막에 합쳐져야 하는 불 그룹)이 같은지 비교하여 판단한다. 만약 그 두 값이 서로 다른 불 그룹이 하나라도 있다면 아직 모든 불이 합쳐지지 않았다고 판단하여 계속해서 반복문을 실행한다.

public static boolean confluence() {
    for (int i = 1; i <= groupMax; i++) {
        if (find(parent[i], grouped) == find(parent[i], parent)) continue;
        else return false;
    }
    return true;
}

 

아무쪼록 3일 내내 고생하며 풀이한 문제였다. 제목에 어그로가 끌려 풀었지만 시간 초과와 메모리 초과를 거치면서 최적화를 고민할 수 있었던 문제인거 같다.

 

아래는 전체 코드이다. (Union Find와 관련된 알고리즘은 별도로 설명하지 않았다. 만약 궁금하다면 아래 글을 참고하면 좋을 것 같다.)

[백준 P1717] 집합의 표현 Java

 

 

코드

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

public class Main {
    static final int[] dr = {-1, 0, 1, 0};
    static final int[] dc = {0, -1, 0, 1};

    static int N, M;
    static int[][] graph;
    static int[][] groupIdx;
    static Queue<int[]> trees;

    static int groupMax;
    static int[] parent;
    static int[] grouped;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        graph = new int[N][M];
        groupIdx = new int[N][M];

        trees = new ArrayDeque<>();

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                graph[i][j] = line.charAt(j) - '0';
            }
        }

        findGroup();

        if (groupMax <= 1) {
            System.out.println("0 " + countFire());
        } else {
            int time = 0;
            unionFire();
            while (!confluence()) {
                goFire();
                time++;
            }
            System.out.println(time + " " + countFire());
        }
    }

    public static void findGroup() {
        Queue<int[]> q = new ArrayDeque<>();
        boolean[][] visited = new boolean[N][M];
        int idx = 1;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (graph[i][j] == 0) {
                    if (!visited[i][j]) {
                        q.add(new int[]{i, j});

                        visited[i][j] = true;
                        groupIdx[i][j] = idx;

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

                            for (int d = 0; d < 4; d++) {
                                int newR = curR + dr[d];
                                int newC = curC + dc[d];

                                if (0 <= newR && newR < N && 0 <= newC && newC < M) {
                                    if (!visited[newR][newC]) {
                                        visited[newR][newC] = true;

                                        if (graph[newR][newC] == 0) {
                                            groupIdx[newR][newC] = idx;
                                            q.add(new int[]{newR, newC});
                                        } else if (graph[newR][newC] == 1) {
                                            trees.add(new int[]{newR, newC});
                                        }
                                    }
                                }
                            }
                        }
                        idx++;
                    }
                }
            }
        }

        groupMax = idx - 1;
    }

    public static void unionFire() {
        Queue<int[]> q = new ArrayDeque<>();
        boolean[][] visited = new boolean[N][M];
        boolean[] searched = new boolean[groupMax + 1];

        parent = new int[groupMax + 1];
        grouped = new int[groupMax + 1];

        for (int i = 1; i <= groupMax; i++) {
            parent[i] = i;
            grouped[i] = i;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!visited[i][j] && graph[i][j] == 0 && !searched[groupIdx[i][j]]) {
                    int groupFlag = groupIdx[i][j];

                    q.add(new int[] {i, j});
                    visited[i][j] = true;
                    searched[groupFlag] = true;

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

                        for (int d = 0; d < 4; d++) {
                            int newR = curR + dr[d];
                            int newC = curC + dc[d];

                            if (0 <= newR && newR < N && 0 <= newC && newC < M) {
                                if (!visited[newR][newC] && graph[newR][newC] != 2) {
                                    visited[newR][newC] = true;

                                    if (graph[newR][newC] == 0 && groupIdx[newR][newC] != groupFlag && !searched[groupIdx[newR][newC]]) {
                                        searched[groupIdx[newR][newC]] = true;
                                        union(groupFlag, groupIdx[newR][newC], grouped);
                                    }

                                    q.add(new int[] {newR, newC});
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    public static void goFire() {
        Queue<int[]> newTrees = new ArrayDeque<>();
        boolean[][] visited = new boolean[N][M];

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

            graph[curR][curC] = 0;

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

                if (0 <= newR && newR < N && 0 <= newC && newC < M) {
                    if (graph[newR][newC] == 1 && !visited[newR][newC]) {
                        visited[newR][newC] = true;
                        newTrees.add(new int[]{newR, newC});
                    } else if (groupIdx[newR][newC] > 0) {
                        if (groupIdx[curR][curC] == 0) groupIdx[curR][curC] = groupIdx[newR][newC];
                        else {
                            union(groupIdx[newR][newC], groupIdx[curR][curC], parent);
                        }
                    }
                }
            }
        }
        trees = newTrees;
    }

    public static int countFire() {
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (graph[i][j] == 0) cnt++;
            }
        }
        return cnt;
    }

    public static void union(int a, int b, int[] parent) {
        int aParent = find(a, parent);
        int bParent = find(b, parent);

        if (aParent < bParent) {
            parent[bParent] = aParent;
        } else if (bParent < aParent) {
            parent[aParent] = bParent;
        }
    }

    public static int find(int target, int[] parent) {
        if (target == parent[target]) return target;
        else return parent[target] = find(parent[target], parent);
    }

    public static boolean confluence() {
        for (int i = 1; i <= groupMax; i++) {
            if (find(parent[i], grouped) == find(parent[i], parent)) continue;
            else return false;
        }
        return true;
    }
}