[3197] 백조의 호수

문제 링크 : https://www.acmicpc.net/problem/3197

3197 - 백조의 호수

본문

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

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

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

아래에는 세 가지 예가 있다.

...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... 
....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... 
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X..... 
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX.... 
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX.... 
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............ 
..XXXXX...XXX.... ....XX.....X..... ................. 
....XXXXX.XXX.... .....XX....X..... ................. 
      처음               첫째 날             둘째 날

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

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

입력

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

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

출력

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

제한

시간 제한	메모리 제한
1sec	256MB

풀이

빙판이 없어졌을 때 경로를 찾는 것처럼 보이므로 단순하게 BFS 탐색을 진행하면 될 것 같다. 그런데 칸의 수가 $1500 \times 1500 = 2\,250\,000$개, 시간상 모든 칸을 탐색한다면 최대 2번까지 돌 수 있을 것 같다. 단순 시뮬레이션으로는 풀 수 없다는 뜻.

그럼 탐색 횟수를 줄여보자. 칸을 2번씩만 방문할 수 있으므로, BFS는 1번만 순회하도록 하자. BFS 진행 중에 특정 칸을 꺼내서 4방향을 다시 탐색해야되기 때문에, 방문 횟수는 최대 2번까지 가능하지만 시간상 1번밖에 못 돌릴 확률이 크다. 모든 칸은 1번만 방문하는 것으로 계획을 세워보자.

그렇다면 할 수 있는 방법이 있다. 물이 입력된다면 pass, 빙판이 입력된다면, 그 칸이 어느 시점 이후에 없어지는지 확인할 수 있으면 된다. 즉 물이 입력되었을 때 주위의 빙판을 녹일 것이므로 그 빙판들은 1이 기록될 것이고, 물에서부터 시작하는 BFS가 있다면 빙판이 어느 시점에 없어지는지 계산할 수 있다. 이러면 BFS를 이용하여 모든 칸을 2번씩 돌았다. ( BFS에 넣는 것 1번, 꺼내서 4방향을 다시 탐색하므로 시간상 1번을 더 사용한다 )

그래서 더 이상 칸을 탐색하는 과정을 넣는 것은 위험하다. 그런데 이렇게 구현하면 어느 시점에 백조가 서로 닿을 수 있는지 확인할 수가 없다. 백조끼리 연결하기 위해서 BFS를 다시 탐색해야하기 때문. 이 경우 BFS를 칸의 최대 개수인 225만번 돌려야할 수도 있다. 당연히 말이 안되는 수치. 칸을 다시 탐색하지 않고 백조가 서로 만날 수 있는지 확인할 수 있는 과정을 거쳐야한다.

백조는 물 위에서는 그 어떤 위치도 돌아다닐 수 있다. 사실상 백조가 다닐 수 있는 물의 공간은 물 1칸으로 생각해도 된다는 것. 프로그래밍적으로 생각해보면, 백조가 있는 물의 공간은 하나의 그룹으로 쳐도 된다는 것을 의미한다. 여기서 사용할 수 있는 방법이 “유니온 파인드”가 될 것이다. 모든 칸이 parent를 가지고 있는 유니온파인드를 구현하도록 하자. parent가 같으면 같은 그룹에 속해있다는 뜻으로, 같은 그룹에 속한 물 공간은 그 어떤 곳이든 같은 그룹이면 이동할 수 있다는 뜻으로 해석할 수 있다.

이정도까지 생각했으면 그림이 그려진다. 구현점은 아래와 같다.

칸을 탐색하는 BFS를 구현할 것이다. 다만 모든 칸은 1번씩만 탐색할 예정이다
- 이 조건때문에, 일반적인 BFS 탐색이 아닌 다른 방법을 사용해야한다
물의 공간에서 어떤 칸으로 자유롭게 이동할 수 있는지 빠르게 확인하기 위해 모든 칸에 대해 유니온파인드를 구현한다
- parent가 같은 두 칸은 자유자재로 다닐 수 있다는 것을 의미한다
- 즉, 백조가 자유롭게 오갈 수 있는 상황을 판단하는 요소가 백조가 있는 두 칸의 parent가 같은지 조건과 같다

유니온파인드를 사용한다면 BFS 탐색을 하는 궁극적인 목적이 ‘백조가 서로 이어질 수 있는가’ 가 아니라, ‘빙판이 어느 시점에 녹아 사라질 것인가’가 된다. 사실상 find함수 2번이면 백조가 이어지는지 확인할 수 있으므로, 빙판이 언제 녹아 없어지고, 물의 공간이 서로 이어지는지 확인하는 것이 BFS 함수의 목적이다. 그래서, BFS의 시작지점은 백조의 위치가 아닌, 물이 있는 공간들이 된다. 처음은 물들을 전부 그룹으로 묶는 merge를 실행해야할 것이다. 그리고 물과 인접한 빙판들을 따로 빼서 기록해두어야할 것이다. 그 빙판들은 시간이 한번 지나면 녹아서 물이 될 것이기 때문이다. BFS를 1번만 돌린다고 했으므로, 이 과정은 동시에 이루어져야한다. 물에 대한 연산이 모두 끝나면 다음은 기록해둔 빙판에 대한 연산을 진행하도록 한다. 기록되어있는 빙판들은 물로 바꾸고, 옆에 있는 물과 다시 merge하여 같은 그룹으로 묶어주고, 옆의 빙판은 또 따로 기록하여 다음 시간에 녹는 것을 체크할 수 있도록 해야한다. 시간 1번마다 탐색중인 칸이 따로, 기록해야하는 칸이 따로 있으니까 BFS를 위한 큐를 2개 만들면 관리하기 편할 것 같다.

그런데 여기서 문제가 발생한다. 메모리 제한에 걸려버린 것이다. 생각해보면 225만개의 칸을 가진 배열을 많이 만들었다.

grid를 위한 char 배열 (225만 byte)
visit 체크를 위한 bool 배열 (225만 byte)
유니온파인드를 위한 int 배열 (225만 byte x $4$)
BFS를 위한 큐 2개 (225만 byte x $8$)

이것들 때문에 메모리에서 제한에 걸리는 것 같다. 메모리를 줄여야한다는 문제에 직면했다. 이게 vector<>를 사용했다면 좋은 방법일 수도 있었는데, C에서 배열의 크기를 임의조절하기가 힘들어서 생기는 문제라고 생각했다.

메모리를 줄이기 위해, 필수적으로 써야 하는 배열을 생각해보자. 일단 입력으로 사용하는 grid, 유니온파인드를 위한 int배열은 필수다. 큐는 2개를 사용하는 것이 관리하기 편한데, 모든 칸은 1번만 탐색하기로 하였으니 사실 큐가 1개만 있어도 모든 상황을 파악할 수 있었다. BFS를 1번만 탐색하도록 아이디어를 짠 것이 이득이 되었다! 또, visit 체크를 따로 배열을 만들지 않아도 grid를 이용하여 할 수 있을 것 같다. 이미 방문했다면 그 칸은 빙판이 녹아 물이 되었을 것이기 때문이다. visit 배열도 제거해보자.

즉 사용하는 배열이 grid와 parent, 그리고 큐 1개 해서 총 3개뿐이다. 이렇게 하니 메모리 제한에 거의 닿아버리는 것을 알 수 있었다.

사용할 알고리즘이 다 정해졌으므로 flow를 짜보도록 하자.

입력으로 주어지는 칸을 전부 돌아본다. 그 중 물이 있는 칸을 그룹으로 묶기 위해 따로 기록해둔다
물이 있는 칸에 대해서 연산을 수행한다 ( 현재 큐의 rear까지만 )
- 주위에 있는 물들과는 그룹을 묶어준다
- 주위에 있는 빙판은 큐에 기록하여 다음 시간에 녹는다는 것을 기록한다
빙판이 남아있다면 계속해서 반복한다
- “종료 조건”을 탐색한다 ( 백조가 서로 만날 수 있는가? = 백조가 현재 같은 그룹에 존재하는가? )
  - 만약 종료조건에 도달하였다면 그 epoch를 출력한다
- 기록되어있는 빙판을 녹이는 작업을 수행한다 ( 현재 큐의 rear까지이다 )
  - 기록되어있던 빙판은 물로 바뀐다
  - 위에서 물 칸에 대해 했던 작업을 똑같이 수행한다
    - 주위의 물과는 그룹으로 묶는다
    - 주위의 탐색하지 않은 빙판은 큐에 기록한다

이 과정을 수행하면 메모리를 아끼고, 시간도 아낀 해결방법을 얻을 수 있다.

참고 알고리즘 : 분리 집합, BFS 탐색

코드

사용 언어 : C
최종 수정일 : 2023 / 4 / 11

  
#include <stdio.h>

typedef char bool;
const bool true = 1;
const bool false = 0;

typedef struct Node {
    int x, y;
} ND;

#define MAX_IDX 1500
char grid[MAX_IDX][MAX_IDX + 1];
int parent[MAX_IDX * MAX_IDX + 1];
int r, c;

#define WALL 'X'
#define VISITED 'V'
#define BLANK '.'
#define BIRD 'L'

#define MAX_DIR 4
ND dir[MAX_DIR] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

ND bird[2];
bool firstBirdAppeared = false;

ND queue[MAX_IDX * MAX_IDX + 1];
int front, rear, endLine;

const int FIRST = 0;
const int SECOND = 1;

bool isValidPosition(ND a) { return (0 <= a.x && a.x < r && 0 <= a.y && a.y < c); }
int IP(ND a) { return a.x * c + a.y; }

int find(int x) {
    if (x == parent[x]) {
        return x;
    } else {
        return parent[x] = find(parent[x]);
    }
}
void merge(int a, int b) {
    int x = find(a), y = find(b);
    if (x != y) {
        parent[y] = parent[b] = x;
    }
    return;
}

void melt() {
    while (front < endLine) {
        ND cur = queue[front++];
        grid[cur.x][cur.y] = BLANK;

        for (int i = 0; i < MAX_DIR; ++i) {
            ND next = (ND){cur.x + dir[i].x, cur.y + dir[i].y};
            if (isValidPosition(next)) {
                switch (grid[next.x][next.y]) {
                    case BLANK: {
                        merge(IP(next), IP(cur));
                        break;
                    }
                    case WALL: {
                        if (grid[next.x][next.y] == WALL) {
                            grid[next.x][next.y] = VISITED;
                            queue[rear++] = next;
                            break;
                        }
                    }
                }
            }
        }
    }
    return;
}

int main() {
    scanf("%d %d", &r, &c);
    for (int i = 0; i < r; ++i) {
        scanf("%s", grid[i]);
        for (int j = 0; j < c; ++j) {
            parent[IP((ND){i, j})] = IP((ND){i, j});
        }
    }

    // blank group init
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            switch (grid[i][j]) {
                case BIRD: {
                    bird[firstBirdAppeared++] = (ND){i, j};
                    grid[i][j] = BLANK;
                }
                case BLANK: {
                    queue[rear++] = (ND){i, j};
                    break;
                }
                case WALL: {
                    break;
                }
            }
        }
    }

    // make group (blank)
    endLine = rear;
    while (front < endLine) {
        ND cur = queue[front++];

        for (int i = 0; i < MAX_DIR; ++i) {
            ND next = (ND){cur.x + dir[i].x, cur.y + dir[i].y};
            if (isValidPosition(next)) {
                if (grid[next.x][next.y] == WALL) {
                    grid[next.x][next.y] = VISITED;
                    queue[rear++] = next;
                } else if (grid[next.x][next.y] == BLANK) {
                    merge(IP(cur), IP(next));
                }
            }
        }
    }

    // melting operations
    for (int i = 0; i <= r * c; ++i) {
        if (find(IP(bird[FIRST])) == find(IP(bird[SECOND]))) {
            printf("%d", i);
            break;
        }

        endLine = rear;
        melt();
    }

    return 0;
}

[3197] 백조의 호수

3197 - 백조의 호수

본문

입력

출력

제한

풀이

코드

Further Reading

[1916] 최소비용 구하기

[15686] 치킨 배달

[1253] 좋다