[백준/BOJ] 백준 15559번 : 내 선물을 받아줘

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

15559번: 내 선물을 받아줘

유니온 파인드를 이용해 이동할 수 있는 칸들을 같은 구역으로 합친 뒤, 총 구역이 몇 개인지를 구해 문제를 해결했다.

 

코드

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

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

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

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 (rank_size[u] < rank_size[v])
	{
		parent[u] = v;
	}

	else
	{
		parent[v] = u;

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

void Dfs(pair<int, int> here)
{
	int here_number = here.first * m + here.second; //좌표를 숫자로 표현

	visited[here_number] = 1;

	pair<int, int> there;

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

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

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

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

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

	if (Find(here_number) != Find(there_number))
		Merge(here_number, there_number);

	if (visited[there_number] == 0)
	{
		Dfs(there);
	}
}

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

	Pre();

	cin >> n >> m;

	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*m + j] == 0)
			{
				Dfs(make_pair(i, j));
			}
		}
	}

	set<int> result_check;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			int u = Find(i * m + j);
			result_check.insert(u);
		}
	}

	cout << result_check.size();

	return 0;
}