골드2 - 백준 16724 피리 부는 사나이

백준 16724 피리 부는 사나이

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

접근방법

이 문제는 마을이 몇개의 집합으로 나뉘는 지 구하는 문제였고, 분리집합을 이용하여 풀 수 있었다. DFS를 통해서 재귀적으로 주어진 방향대로 따라갔고, 이미 방문한 지점을 만나면 그 지점이 속해있는 집합과 합쳐주었고, 총 집합의 개수를 구할 수 있었다.

풀이

마을의 첫 지점부터 순회하면서 아직 속해있는 집합이 없는 곳을 출발점으로 하여 DFS를 진행시켰다. cnt를 하나씩 늘리며 집합을 구분해주었다.
DFS는 현재 위치를 cnt로 우선 초기화를 해주었고, 방향에 따라 다음 지점을 구해주었다. 아직 속해있는 집합이 없다면 계속해서 DFS를 진행시켰고, 만약 다음 지점이 집합이 이미 정해져있는 지점이라면 현재 위치를 그 집합의 값으로 다시 초기화를 해주고 재귀를 거슬러 올라가면서 집합을 합쳐주었다.
모든 지점에 집합값이 정해지면 총 몇개의 집합인지 세어주어야하는데 단순히 cnt값으로 하면 중간에 합쳐진 집합을 구분할 수 없어서 check 배열을 사용해주었다. board 배열을 전체적으로 순회하면서 해당 집합값이 아직 세어지지 않았다면 result에 1을 더해주고, 이미 세어진 집합값이면 건너뛰어주었다.

코드

#include <iostream>
#include <vector>

using namespace std;

int board[1000][1000];
vector<string> b;
bool check[1000100];

int DFS(int x, int y, int cnt)
{
	board[x][y] = cnt;

	int nx = x, ny = y;
	switch (b[x][y])
	{
	case 'D':
		nx += 1;
		break;

	case 'L':
		ny -= 1;
		break;

	case 'R':
		ny += 1;
		break;

	case 'U':
		nx -= 1;
	}

	if (board[nx][ny] != 0)
		return board[x][y] = board[nx][ny];
	return board[x][y] = DFS(nx, ny, cnt);
}

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

	int N, M;
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		string temp;
		cin >> temp;
		b.push_back(temp);
	}

	int cnt = 1;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (board[i][j] != 0)
				continue;

			board[i][j] = cnt;
			DFS(i, j, cnt);
			cnt++;
		}
	}

	int result = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (!check[board[i][j]])
			{
				result++;
				check[board[i][j]] = true;
			}
		}
	}

	cout << result << endl;

	return 0;
}