[BOJ16724] 피리 부는 사나이

문제가 무슨 말인지를 몰라서 푸는 데 시간이 걸리는 문제이다.

힌트는 주어져 있지만...

약간, DFS와 Disjoint Set이 필요한 이유를 찾아보기는 힘들지만, 

전에 이야기하듯이, find와 merge를 이용하면 쉬운 문제이다.

즉, find에서는 부모 배열에서 같은 값이 있으면 그 값을 리턴하면 되지만, 없으면 

자식이 있을 때까지 찾는 것이다.

즉, 만약 자식을 찾으면 merge에서 x와 y가 같으면 끝이지만, 아니라면 SAFE ZONE이 될 수 없다는 의미인 거 같다.

x = (i * m + j)로 주로 맡는다.

그럼 y는?

y는 상하좌우 역할을 맡게 하면 된다.

 

여러 경우로 나눈 거 보면 얼핏 DFS와 유사해보인다.

DFS는 Depth기준으로 하여 경우를 찾는 것을 말한다.

긴 if문을 단순하게 만들 수 있다는 장점이 있기도 해서 유용한 알고리즘이다.

 

하지만, disjoint set으로 이용해야 하므로,

c++에서 제공하는 set으로 이용한다.

find(i * m + j)를 불러와서 찾은 자식들의 값을 set에 저장하면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int n, m;
char map[1001][1001];
int parent[1000001];
int find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}
void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    parent[x] = y;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
    for (int i = 0; i < n * m; i++) {
        parent[i] = i;
    }
    
    // 상하좌우
    // 방향이 상이면 i*m+j와 (i-1)*m+j를 합친다.
    // 방향이 하이면 i*m+j와 (i+1)*m+j를 합친다.
    // 방향이 좌이면 i*m+j와 i*m+j-1를 합친다.
    // 방향이 우이면 i*m+j와 i*m+j+1를 합친다.

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 'U') {
                merge(i * m + j, (i - 1) * m + j);
            } else if (map[i][j] == 'D') {
                merge(i * m + j, (i + 1) * m + j);
            } else if (map[i][j] == 'L') {
                merge(i * m + j, i * m + j - 1);
            } else if (map[i][j] == 'R') {
                merge(i * m + j, i * m + j + 1);
            }
        }
    }
    set<int> s;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            s.insert(find(i * m + j));
        }
    }
    cout << s.size() << endl;
    return 0;
}

시간 복잡도: O(NM)

 

소스는 참고용으로 쓰기를...