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

출처 : https://www.acmicpc.net/problem/16724

 

유니온 파인드를 이용해서 몇개의 집합으로 나누어져 있는지 구했다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n, m;

int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };

vector<int> parent;
vector<int> height;
vector<vector<int>> board;

pair<int, int> Index2RowCol(int idx) {
    int row = idx / m;
    int col = idx - (row * m);
    return { row,col };
}

int RowCol2Index(pair<int, int> rowcol) {
    int row = rowcol.first;
    int col = rowcol.second;
    return row * m + col;
}

int GetParent(int n) {
    if (n == parent[n])
        return n;
    return parent[n] = GetParent(parent[n]);
}

void Merge(int u, int v) {
    u = GetParent(u);
    v = GetParent(v);

    if (u == v)
        return;

    if (height[u] > height[v])
        ::swap(u, v);

    parent[u] = v;

    if (height[u] == height[v])
        height[v]++;
}

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

    cin >> n >> m;
    parent = vector<int>(n * m);
    height = vector<int>(n * m, 1);
    board = vector<vector<int>>(n, vector<int>(m));
    for (int i = 0; i < n * m; i++) {
        parent[i] = i;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char direction;
            cin >> direction;
            switch (direction) {
            case 'U':
                board[i][j] = 0;
                break;
            case 'R':
                board[i][j] = 1;
                break;
            case 'D':
                board[i][j] = 2;
                break;
            case 'L':
                board[i][j] = 3;
                break;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int currRow = i;
            int currCol = j;
            int dir = board[currRow][currCol];
            int nextRow = currRow + dRow[dir];
            int nextCol = currCol + dCol[dir];
            
            int currIdx = RowCol2Index({ currRow,currCol });
            int nextIdx = RowCol2Index({ nextRow,nextCol });

            Merge(currIdx, nextIdx);
        }
    }
    set<int> s;
    for (int i = 0; i < n * m; i++) {
        s.insert(GetParent(i));
    }
    cout << s.size();
}