[백준] 15559 - 내 선물을 받아줘

https://www.acmicpc.net/problem/15559

15559번: 내 선물을 받아줘

 

우선 모든 경우의 수를 전부 탐색하는 경우를 생각해 보자. 예제 1번에서,

(1, 1)에서 시작하면 가장자리의 모든 수를 방문하게 된다.

(1, 2)에서 시작해도 가장자리의 모든 수를 방문하게 된다.

(1, 3)에서 시작해도 가장자리의 모든 수를 방문하게 된다.

..

 

따라서, 어떤 점에서 시작해서 방문한 이력이 있는 곳을 방문했을 때 그 이후에는 방문하지 않아도 된다는 뜻이다.

즉, 주어진 지도에서 각 점을 정점으로 생각하고, 그래프의 개수를 구하면 되는 문제이다.

 

그런데 예제 입력 1에서는 가장자리 그래프 1개, (2, 2)와 (2, 3)을 정점으로 가지는 그래프 1개 총 그래프 2개가 생성된다.

이 각 그래프가 서로 다른 그래프인지 어떻게 판별해야 할까?

 

int형 변수 하나로 새로운 출발을 시작할 때마다 값을 늘려가며 방문하면 된다. 그런데 이렇게 하면 다음과 같은 예제에서 문제가 생긴다.

1 4
WWWW

 

이 경우에서 답은 1임에도 불구하고 방문 배열은 다음과 같이 될 것이다.

1234

 

즉, 1 2 3 4가 모두 같은 그래프 내에 속해야 한다.

우리는 이것을 Union Find로 해결하려고 한다. 즉, 어떤 정점에서 출발해서 이미 방문한 이력이 있는 곳을 방문했을 때 Union 하면 이전 방문한 정점에 포함된 그래프와 지금 방문한 정점에 포함된 그래프가 서로 합쳐지게 될 것이다.

이렇게 하면 순수한 그래프의 개수를 구할 수 있다.

 

#include <iostream>
#include <map>
#include <set>
using namespace std;

int p[1000000];
int n, m, vis[1001][1001];
char board[1001][1001];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
map<char, int> ma = {{'N', 3}, {'S', 2}, {'W', 1}, {'E', 0}};

int Find(int x) {
    if (p[x] == x) {
        return x;
    }
    return p[x] = Find(p[x]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    p[a] = b;
}

bool range(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> board[i][j];
        }
    }
    for (int i = 1; i <= n * m; i++) {
        p[i] = i;
    }
    int parent = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!vis[i][j]) {
                int x = i, y = j;
                while (!vis[x][y] && range(x, y)) {
                    vis[x][y] = parent;
                    int nx = x + dx[ma[board[x][y]]];
                    int ny = y + dy[ma[board[x][y]]];
                    x = nx, y = ny;
                }
                if (range(x, y)) {
                    Union(vis[i][j], vis[x][y]);
                }
                parent++;
            }
        }
    }
    set<int> se;
    for (int i = 1; i < parent; i++) {
        se.insert(Find(i));
    }
    cout << se.size();
}