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

백준 16724번: 피리 부는 사나이
알고리즘 분류: 자료 구조, 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 분리 집합

백준 문제 바로가기

🤨 Hmm...

이 문제의 첫 트라이는 dfs + 분리집합으로 풀었다.

이렇게 하니까 메모리도 많이 잡아 먹고 시간도 다른 코드에 비해 오래 걸렸다.

그래서 효율적인 코드를 찾았는데 뭔가 띠용스러웠다.

분리 집합만을 사용해서 애초에 답을 N*M 으로 해놓고 union 연산이 적용되면 -1 하는 방식이다.

그리고 방문 처리도 parent 값을 보면 된다는 것을 다시금 깨달았다.

사고력을 길러야겠다.

💻 소스 코드

#include <iostream>
#include <algorithm>
#define int long long
#define pii pair<int, int>
#define fastIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;

class BJ {
    int N, M;
    char grid[1000][1000];
    pii **parent;
    int answer;
public:
    BJ();
    pii findParent(pii p);
    void unionParent(pii p1, pii p2);
};

BJ::BJ() {
    cin >> N >> M;
    answer = N*M;
    parent = new pii *[N];
    for (int i = 0; i < N; i++) {
        parent[i] = new pii[M];
        for (int j = 0; j < M; j++) {
            cin >> grid[i][j];
            parent[i][j] = {i, j};
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (parent[i][j] != make_pair(i, j)) continue;
            pii p;
            switch (grid[i][j]) {
                case 'U': p = findParent({i-1, j}); break;
                case 'D': p = findParent({i+1, j}); break;
                case 'L': p = findParent({i, j-1}); break;
                default: p = findParent({i, j+1});
            }
            if (p != make_pair(i, j)) {
                parent[i][j] = p;
                answer--;
            }
        }
    }
    cout << answer;
}

pii BJ::findParent(pii p) {
    int r = p.first, c = p.second;
    if (parent[r][c] == make_pair(r, c))
        return {r, c};
    parent[r][c] = findParent(parent[r][c]);
    return parent[r][c];
}
void BJ::unionParent(pii p1, pii p2) {
    pii px = findParent(p1);
    pii py = findParent(p2);
    parent[py.first][py.second] = px;
}

signed main(){
    fastIO;

    BJ Q16724;
}