[백준 P3197] 백조의 호수 Java

P3197 백조의 호수

3197번: 백조의 호수

문제

두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.

호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.

호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다. 아래에는 세 가지 예가 있다.

백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.

며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.

 

입력값

입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.

다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

10 2
.L
..
XX
XX
XX
XX
XX
XX
..
.L

4 11
..XXX...X..
.X.XXX...L.
....XXX..X.
X.L..XXX...

8 17
...XXXXXX..XX.XXX
....XXXXXXXXX.XXX
...XXXXXXXXXXXX..
..XXXXX.LXXXXXX..
.XXXXXX..XXXXXX..
XXXXXXX...XXXX...
..XXXXX...XXX....
....XXXXX.XXXL...

 

출력값

첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.

3

2

2

 

알고리즘

백조는 얼음 위를 걸어갈 수 없나..? 라는 의문을 가지며 문제를 풀었다.

우선 문제의 조건과 구해야 하는 결과를 정리하면 다음과 같다.

1. 물에 접촉한 빙판은 모두 녹는다.
2. 백조가 며칠이 지나야 만날 수 있는지 출력한다.

그래서 물에 접촉한 빙판을 녹이는 메서드와 백조가 서로 만날 수 있는지 (얼음에 가로막히지 않은 길이 있는지) 판단하는 메서드를 만들어야 한다.

 

우선 두 마리의 백조가 서로 만날 수 있는지 판단하는 부분은 유니온 파인드 알고리즘을 사용했다. 얼음에 막혀있지 않고 서로 인접한 물을 하나의 그룹으로 보고 R x C 호수를 모두 탐색하며 몇 개의 그룹이 있는지 구하고 groupIdx라는 배열에 특정 좌표가 몇 번째 그룹에 속하는지를 기록한다. 예를 들어, 호수가 위와 같이 구성되어 있다면 groupIdx는 다음과 같을 것이다.

 

이렇게 그룹을 나눈 뒤에, 백조 두마리의 위치를 저장한다. 시간이 지남에 따라 얼음을 녹이면서 두 마리의 백조가 속한 그룹이 (groupIdx 값) 서로 같은 집합인지 확인하면 된다.

 

물에 접촉한 빙판을 녹이는 메서드는 큐를 사용했다. 큐 안에는 4방(위, 아래, 왼쪽, 오른쪽) 중에서 한개 이상의 방향에 물이 있어서 녹게되는 빙산들이 저장되어 있다. 큐에서 녹아야 하는 얼음을 하나씩 뽑고, 그 얼음을 녹은 것으로 바꾸어준다. 이제 빙산이 녹아 물이 되었으므로 그 부분에서 또 4방 탐색을 하며 이번에 빙산이 녹았기 때문에 다음 번에 녹게되는 새로운 빙산을 큐에 담는다.

 

빙산을 녹일 때 한 가지 일을 더 수행해야 한다. 바로 빙산이 녹은 뒤에 그 빙산의 groupIdx를 업데이트 해주고, 그 빙산이 녹음으로서 다른 그룹과 만나게 된다면 union 연산을 수행해주면 된다. 녹게되는 빙산(밑에서는 빙산이라고 부르겠다.)의 4방을 탐색하면 반드시 1개 이상의 물이 있을 것이다. 4방 탐색을 하며 물을 발견한 경우에 빙산의 groupIdx값이 0이라면 물의 groupIdx값을 빙산의 groupIdx 값으로 바꾸어준다. 만약 0이 아니라면 두 개의 물 그룹이 빙산이 녹아서 만나게 된 것이므로 빙산의 groupIdx와 물의 groupIdx를 서로 union 해준다.

graph[curR][curC] = '.';

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

    if (0 <= newR && newR < R && 0 <= newC && newC < C) {
        if (graph[newR][newC] == 'X' && !visited[newR][newC]) {
            visited[newR][newC] = true;
            newIces.add(new int[] {newR, newC});
        } else if (graph[newR][newC] == '.') {
            if (groupIdx[curR][curC] == 0) {
                groupIdx[curR][curC] = groupIdx[newR][newC];
            } else {
                union(groupIdx[curR][curC], groupIdx[newR][newC]);
            }
        }
    }
}

두 백조가 서로 같은 물 그룹 집합에 있을 때 까지 반복문을 수행하고 결과를 출력한다.

 

전체 코드는 아래와 같다.

 

코드

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 R, C;
    static int answer;
    static int[] parent;
    static char[][] graph;
    static int[][] swan;
    static int[][] groupIdx;
    static Queue<int[]> ices;

    static int groupMax;

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

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        graph = new char[R][C];
        groupIdx = new int[R][C];
        swan = new int[2][2];

        ices = new ArrayDeque<>();

        int swanIdx = 0;
        for (int r = 0; r < R; r++) {
            String line = br.readLine();
            for (int c = 0; c < C; c++) {
                graph[r][c] = line.charAt(c);
                if (graph[r][c] == 'L') {
                    swan[swanIdx++] = new int[] {r, c};
                    graph[r][c] = '.';
                }
            }
        }

        findIdx();

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

        //2. 백조끼리 비교한다.
        while (find(groupIdx[swan[1][0]][swan[1][1]]) != find(groupIdx[swan[0][0]][swan[0][1]])) {
            //1. 얼음이 녹는다.
            meltingIce();
            answer++;
        }

        System.out.println(answer);
    }

    public static void meltingIce() {
        Queue<int[]> newIces = new ArrayDeque<>();
        boolean[][] visited = new boolean[R][C];

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

            visited[curR][curC] = true;

            graph[curR][curC] = '.';

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

                if (0 <= newR && newR < R && 0 <= newC && newC < C) {
                    if (graph[newR][newC] == 'X' && !visited[newR][newC]) {
                        visited[newR][newC] = true;
                        newIces.add(new int[] {newR, newC});
                    } else if (graph[newR][newC] == '.') {
                        if (groupIdx[curR][curC] == 0) {
                            groupIdx[curR][curC] = groupIdx[newR][newC];
                        } else {
                            union(groupIdx[curR][curC], groupIdx[newR][newC]);
                        }
                    }
                }
            }
        }

        ices = newIces;
    }

    public static void findIdx() {
        Queue<int[]> q = new ArrayDeque<>();
        boolean[][] visited = new boolean[R][C];
        int idx = 1;

        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (!visited[r][c] && graph[r][c] != 'X') {
                    visited[r][c] = true;
                    q.add(new int[] {r, c});
                    groupIdx[r][c] = idx;

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

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

                            if (0 <= newR && newR < R && 0 <= newC && newC < C) {
                                if (!visited[newR][newC]) {
                                    visited[newR][newC] = true;
                                    if (graph[newR][newC] == '.') {
                                        groupIdx[newR][newC] = idx;
                                        q.add(new int[] {newR, newC});
                                    } else {
                                        ices.add(new int[] {newR, newC});
                                    }
                                }
                            }
                        }
                    }

                    idx++;
                }
            }
        }

        groupMax = idx - 1;
    }

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

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

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