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

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

16724번: 피리 부는 사나이

이동이 가능한 구역들은 유니온 파인드의 유니온을 하고, 그룹의 개수가 몇 개인지 구하는 방법으로 문제를 해결했다.

 

코드

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

int n, m;
vector<string> board;
vector<vector<int>> visited(1000, vector<int>(1000, 0));
vector<int> parent(1000000);
vector<int> rank_size(1000000, 1);
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
set<int> check;
int result = 0;

void Pre()
{
	for (int i = 0; i < 1000000; i++)
		parent[i] = i;
}

int Find(int u)
{
	if (parent[u] == u)
		return u;

	return parent[u] = Find(parent[u]);
}

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

	if (u == v)
		return;

	if (rank_size[u] < rank_size[v])
	{
		parent[u] = v;
	}

	else
	{
		parent[v] = u;

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

void Solve(pair<int, int> here)
{
	visited[here.first][here.second] = 1;

	int here_index = here.first * m + here.second;

	pair<int, int> there;

	if (board[here.first][here.second] == 'U')
		there = make_pair(here.first + dxdy[1][0], here.second + dxdy[1][1]);

	else if (board[here.first][here.second] == 'D')
		there = make_pair(here.first + dxdy[3][0], here.second + dxdy[3][1]);

	else if (board[here.first][here.second] == 'L')
		there = make_pair(here.first + dxdy[0][0], here.second + dxdy[0][1]);

	else if (board[here.first][here.second] == 'R')
		there = make_pair(here.first + dxdy[2][0], here.second + dxdy[2][1]);

	int there_index = there.first * m + there.second;

	//이동할수 있는 구역들은 유니온 한다
	Merge(here_index, there_index);

	if (visited[there.first][there.second] == 0)
		Solve(there);
}

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

	cin >> n >> m;

	Pre();

	for (int i = 0; i < n; i++)
	{
		string input;
		cin >> input;

		board.push_back(input);
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (visited[i][j] == 0)
			{
				Solve(make_pair(i, j));
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			int here_index = i * m + j;
			int here_parent = Find(here_index);

			check.insert(here_parent);
		}
	}

	//그룹의 개수가 몇개인지 구한다
	result = check.size();

	cout << result;
}