[C++] 백준 16724번: 피리 부는 사나이

문제 링크

16724번: 피리 부는 사나이

문제 요약

피리를 불면 모든 사람들이 현재 칸에 적혀진 방향으로 이동하게 된다. 이러한 이동을 멈추기 위해서 안전 장소를 설치하고자 한다. 지도 위의 어떤 구역에 있더라도 안전 장소로 들어갈 수 있도록 하기 위한 최소 안전 장소의 수를 구해야 한다.

접근 방법

각 칸을 이동하면서 방문하지 않은 칸이 있다면 해당 칸부터 그래프 탐색을 돌립니다. 지도 밖으로 나가는 입력은 주어지지 않기 때문에, 현 위치에서 출발해서 방문하는 칸들 중에 한 곳에 안전 장소를 설치하면 됩니다.

그래프 탐색을 하면서 인접한 칸과 만날 때마다 Union-Find를 통해서 현재 칸과 해당 칸을 합쳐줍니다. 만약에 인접한 칸이 방문한 적이 있는 칸이라면, 일단 합친 뒤에 return을 해주면 됩니다. 최종적으로 완성된 Disjoint-set의 수를 세어주면 되는 간단한 문제입니다.

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1001;
pair<int, int> parent[MAX][MAX];
char b[MAX][MAX];
bool visited[MAX][MAX];

pair<int, int> Find(pair<int, int> p) {
    if(parent[p.first][p.second] == p) {
        return p;
    }
    return parent[p.first][p.second] = Find(parent[p.first][p.second]);
}

void Union(pair<int, int> a, pair<int, int> b) {
    auto pa = Find(a), pb = Find(b);

    if(pa != pb) {
        parent[pa.first][pa.second] = pb;
    }
}

void dfs(int r, int c) {
    visited[r][c] = true;

    int nr = r, nc = c;
    switch(b[r][c]) {
        case 'U':
            nr--;
            break;
        case 'D':
            nr++;
            break;
        case 'L':
            nc--;
            break;
        default:
            nc++;
    }

    if(Find({r, c}) != Find({nr, nc})) {
        Union({r, c}, {nr, nc});
    }

    if(visited[nr][nc]) {
        return;
    }

    dfs(nr, nc);
}

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

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

    for(int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> b[i][j];
            parent[i][j] = {i, j};
        }
    }

    for(int i = 1; i <= n; i++)  {
        for(int j = 1; j <= m; j++) {
            if(!visited[i][j]) {
                dfs(i, j);
            }
        }
    }

    int ans = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            ans += (parent[i][j] == make_pair(i, j));
        }
    }

    cout << ans << '\n';
    return 0;
}