[백준 16724 c++] 피리부는 사나이

 

문제를 쉽게 해석하면

-> 사이클의 개수를 찾아라! 

-> 사이클과 연결된 간선은 공짜!

---

 

안전구역이 최소로 구성되기 위해서는, 사이클 내에 1개의 안전구역이 배치되면 조건이 만족한다.

 

또한, 그 안전구역이 생긴 사이클에 접근하는 단방향 간선은 사이클에 포함되도록 설정한다.

 

dfs를 활용하여 수 조건을 알맞게 하면 풀 수 있는 쉬운 문제이다.

 

#include <iostream>
#include <string>

char map[1001][1001] = {};
int vi[1001][1001] = {};

int ans = 0;
int n, m;
void dfs(int x, int y, int cnt) {
	if (map[x][y] == 'D' && x + 1 < n) {
		if (!vi[x + 1][y]) {
			vi[x + 1][y] = cnt;
			dfs(x + 1, y, cnt);
		}
		else if (vi[x + 1][y] == cnt) {
			ans++;
			return;
		}
	}
	else if (map[x][y] == 'L' && y - 1 >= 0) {
		if (!vi[x][y-1]) {
			vi[x][y-1] = cnt;
			dfs(x, y-1, cnt);
		}
		else if (vi[x][y-1] == cnt) {
			ans++;
			return;
		}
	}
	else if (map[x][y] == 'R' && y + 1 < m) {
		if (!vi[x][y + 1]) {
			vi[x][y + 1] = cnt;
			dfs(x, y + 1, cnt);
		}
		else if (vi[x][y + 1] == cnt) {
			ans++;
			return;
		}
	}
	else if (map[x][y] == 'U' && x - 1 >= 0) {
		if (!vi[x-1][y]) {
			vi[x-1][y] = cnt;
			dfs(x-1, y, cnt);
		}
		else if (vi[x-1][y] == cnt) {
			ans++;
			return;
		}
	}
}

int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);

	std::cin >> n >> m;

	std::string tmp;
	for (int i{ 0 }; i < n; i++) {
		std::cin >> tmp;
		for (int j{ 0 }; j < m; j++) {
			map[i][j] = tmp[j];
		}
	}

	int k = 1;
	for (int i{ 0 }; i < n; i++) {
		for (int j{ 0 }; j < m; j++) {
			if (!vi[i][j]) {
				vi[i][j] = k;
				dfs(i, j, k++);
			}
		}
	}
	
	std::cout << ans << "\n";
}