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

경로 집합이 몇 개인지 구하는 문제이다.

 

safe zone은 각 경로의 맨 마지막 도착지점에 만들어질텐데 그 도착지점을 구할 필요는 없다.

따라서 모든 safe zone은 모든 경로 집합의 맨 마지막 노드에 만들어질테니, 경로의 종류가 몇개인지 구하면 된다.

 

따라서 Union Find + DFS로 구해주면 된다.

 

마지막에 모든 부모-자식 depth를 1로 만들어주기 위해서

최종적인 경로압축을 위해 find_parent를 모든 노드에 수행해주고

for (int i = 0; i < N * M; i++)
{
	find_parent(i);
}

 

unordered_set을 활용하여 몇 개의 집합이 존재하는지 구해주면 된다.

 

---

#include <iostream>
#include <vector>
#include <queue>
#include <bitset>
#include <unordered_set>

using namespace std;

#define SIZE 1001

int N, M;
char map[SIZE][SIZE];
bitset<SIZE> visited[SIZE];
int parent[1000001];

int find_parent(int x)
{
    if (parent[x] == x)
    {
        return x;
    }

    return parent[x] = find_parent(parent[x]);
}

void update_parent(int x, int y)
{
    x = find_parent(x);
    y = find_parent(y);

    if (x != y)
    {
        parent[y] = x;
    }
}

void dfs(int y, int x)
{
    visited[y][x] = 1;

    int idx = y * M + x;

    int nexty = y;
    int nextx = x;

    switch (map[y][x])
    {
    case 'U':
        nexty--;
        break;
    case 'D':
        nexty++;
        break;
    case 'R':
        nextx++;
        break;
    case 'L':
        nextx--;
        break;
    }

    int nextidx = nexty * M + nextx;
    update_parent(idx, nextidx);

    // 아직 방문을 안했다면
    if (!visited[nexty][nextx])
    {
        dfs(nexty, nextx);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    for (int i = 0; i < N * M; i++)
    {
        parent[i] = i;
    }

    char ch;
    for (int i = 0; i < N; i++)
    {
        for (int k = 0; k < M; k++)
        {
            cin >> ch;
            map[i][k] = ch;
        }
    }

    for (int i = 0; i < N; i++)
    {
        for (int k = 0; k < M; k++)
        {
            // 아직 방문하지 않았으면
            if (!visited[i][k])
            {
                dfs(i, k);
            }
        }
    }

    // 모든 부모 자식 depth 1로
    for (int i = 0; i < N * M; i++)
    {
        find_parent(i);
    }

    unordered_set<int> set;
    for (int i = 0; i < N * M; i++)
    {
        set.insert(parent[i]);
    }

    cout << set.size();

    return 0;
}