백준 - 피리 부는 사나이 (16724) [C++]

이 문제는 유니온 파인드를 이용해서 풀었다.

 

처음에는 dfs를 이용해서 그룹 수를 찾으면 되겠다고 생각했지만, 이는 정확한 정보를 주지 못한다.

D L L L
D   U
R R U

와 같은 경우 만약 (0, 0)부터 탐색을 돌 경우 왼쪽 원에만 visited가 true가 되고 맨 오른쪽 L는 적용되지 않는다. 따라서 그룹이 2개가 나오게 된다. 그러나 전체가 그룹 하나로 이루어져야 정답이 된다.

 

따라서 이 같은 경우를 없애기 위해 유니온 파인드로 그룹화를 했다. 각 좌표에 대해 번호를 매기고, 이 번호를 토대로 그룹화를 하여 쉽게 문제를 풀 수 있었다.

 

주의할 점은 safe zone의 개수를 구할 때 set를 사용하면 시간 초과가 난다는 점이다. 단순히 for문 두개로 푸니 정답이 나왔다.

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

#define MAX 1000

int N, M;
int parent[MAX * MAX];
char board[MAX][MAX];
map<pair<int, int>, int> boardToNumber;

void init() {
	for (int i = 0; i < N * M; i++) {
		parent[i] = i;
	}
}

int find(int x) {
	if (parent[x] != x) {
		return parent[x] = find(parent[x]);
	}
	return x;
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) {
		return;
	}
	if (a < b) {
		parent[b] = a;
	} else {
		parent[a] = b;
	}
}

void input() {
	int cnt = 0;
	cin >> N >> M;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> board[y][x];
			boardToNumber[{y, x}] = cnt;
			cnt++;
		}
	}
}

int oppositeNumber(int y, int x) {
	char present = board[y][x];
	switch (present) {
	case 'D':
		y++;
		break;
	case 'U':
		y--;
		break;
	case 'L':
		x--;
		break;
	case 'R':
		x++;
		break;
	}
	return boardToNumber[{y, x}];
}

int countOfZone() {
	int result = 0;
	vector<int> zones(N * M, false);
	for (int i = 0; i < N * M; i++) {
		int present = find(i);
		zones[present] = true;
	}
	for (int i = 0; i < N * M; i++) {
		if (zones[i]) {
			result++;
		}
	}
	return result;
}

int solve() {
	int result = 0;
	init();
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			int present = boardToNumber[{y, x}];
			int opposite = oppositeNumber(y, x);
			merge(present, opposite);
		}
	}
	return countOfZone();
}

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

	input();
	cout << solve() << '\n';

	return 0;
}