[백준 16724] 피리 부는 사나이

 

 DFS와 Union Find를 활용하는 문제. 각 노드가 진행하는 방향도 단방향이고, 지도 밖으로 나가는 방향의 입력도 주어지지 않는다. N과 M의 크기도 최대 1,000이라서 최대 노드의 수 또한 1,000,000이다. 조건이 꽤나 친절하다.

 

 각 노드를 탐색하면서 방문 체크를 해가며 DFS를 돌리게 되면 사이클이든 아니든 끝에 도달하게 되고, 그 경로 상에 있는 모든 노드는 같은 집합으로 처리해 준다. 집합 내에서는 어디서 출발하든 공통적으로 도달하게 되는 한 노드가 있기 때문에, 한 집합에는 하나의 SAFE ZONE만 두면 된다.

 한 노드에 대해 DFS를 끝냈다면 다음 노드를 탐색하는데, 이 때 방문한 노드라면 이전 탐색 과정에서 어떤 집합에 속하게 된 것이므로 DFS를 추가적으로 할 필요가 없다. DFS를 할 때 주의할 점은, 구현하기 나름이겠지만 탐색 중에 다음에 방문하려는 노드가 이미 방문 상태일 경우, 해당 노드의 집합과 union 처리를 해주어야 한다는 것이다. 사이클을 형성하는 집합이 있고, 그 사이클에 단방향으로 향하는 노드 경로를 생각해 보면 된다.

 모든 DFS를 끝내고 나면, find로 각각의 root를 찾아내서 총 몇 개의 집합이 형성되었는지를 확인해서 출력하면 된다. 전체 시간 복잡도는 O(N*M)으로 충분하다.

#include <iostream>
#include <unordered_map>

using namespace std;

int root[1000000];
char matrix[1000][1000];
bool isVisited[1000][1000];

int find(int x) {
    if(root[x] == x) {
        return x;
    } else {
        root[x] = find(root[x]);
        return root[x];
    }
}

void makeUnion(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);

    if(rootX<rootY) {
        root[y] = rootX;
    } else {
        root[x] = rootY;
    }
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            cin >> matrix[i][j];
            root[i*1000 + j] = i*1000 + j;
        }
    }

    int curY, curX, curInd;
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            curY = i;
            curX = j;
            curInd = i*1000 + j;

            while(!isVisited[curY][curX]) {
                isVisited[curY][curX] = true;

                switch(matrix[curY][curX]) {
                    case 'R': {
                        curX++;
                        break;
                    }
                    case 'D': {
                        curY++;
                        break;
                    }
                    case 'L': {
                        curX--;
                        break;
                    }
                    case 'U': {
                        curY--;
                    }
                }

                makeUnion(curInd, curY * 1000 + curX);   
            }
        }
    }

    unordered_map<int, int> um;

    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            um[find(i*1000+j)]++;
        }
    }

    cout << um.size();
}