[Algorithm] Union Find 알고리즘 (2) (Disjoint Set) - 섬 갯수 구하기

Union Find는 다양하게 응용할 수 있는데, 인접한 새로운 노드값이 진입하였을 때, 그룹으로 묶어주고 그룹의 개수를 출력하는 문제로도 응용가능하다.

Q. Union Find의 고난도 문제로서, 새로운 좌표가 진입하였을 때, 인접하지 않으면 섬의 갯수를 늘려주고, 인접할 경우에는 두 섬을 Union으로 통합하는 문제이다.

#include <iostream>
using namespace std;
int n = 5;
int map[5][5] = { 0 };
int islandCnt;
struct Node {
    int y;
    int x;
};
Node arr[5][5];
Node getBoss(Node tar) {
    if (arr[tar.y][tar.x].y == -1) return tar;
    // 보낸 노드의 y값이 -1이라면, 최종보스이므로 그대로 return 
    Node ret = getBoss(arr[tar.y][tar.x]);
    // 아니라면, -1이 나올 때까지(=최종보스가 나올때까지, 재귀호출)
    arr[tar.y][tar.x] = ret;
    // 직속보스를 최종보스로 변경 (2개 이상 연결되어 있을 경우)
    return ret;
}

void setUnion(Node t1, Node t2) {
    //t1 -> (ny, nx), t2 -> (dy, dx)
    Node a = getBoss(t1); // t1의 최종보스
    Node b = getBoss(t2); // t2의 최종보스
    if (a.y == b.y && a.x == b.x) return;
    // 이미 그룹이 맺어있다면 끝내기(=최종보스가 같다면 끝내기)
    arr[b.y][b.x] = a;
    // t2 좌표에 t1의 최종보스를 넣어주기 
    islandCnt--;
}

void init() {

    for (int y = 0; y < n; y++) {
        for (int x = 0; x < n; x++) {
            arr[y][x].y = -1;
            arr[y][x].x = -1;
        }
    }

}
int main()
{
    //입력값: {2,1}, {1,3}, {2,3}, {3,3}
    init();
    int q;
    cin >> q;

    int direct[4][2] = { -1,0,0,-1,1,0,0,1 }; //위, 왼쪽, 아래, 오른쪽
    for (int i = 0; i < q; i++) {
        int dy, dx;
        cin >> dy >> dx;
        map[dy][dx] = 1;
        islandCnt++;

        for (int t = 0; t < 4; t++) {
            int ny = dy + direct[t][0];
            int nx = dx + direct[t][1];
            if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
            if (map[ny][nx] == 0) continue; // 움직인 방향에 아무 것도 없으면 (= 여전히 0이면)
            setUnion({ ny,nx }, { dy,dx });
        }
    }

    cout << islandCnt++;

    return 0;
}

문제의 원리는 초기화한 (-1,-1)는 최종보스로 보고, 최종보스의 좌표를 저장하는 것이다. 위의 Arr값의 최종보스는 (2,2)가 되는데, 이 경우 Node배열인 Arr 배열에 최종보스의 값을 저장해준다.

이 경우, Union Find를 맺을 때마다, 섬의 수(islandCnt)의 값을 -1씩 빼주어, 인접한 섬의 '덩어리' 갯수를 구할 수가 있다.