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

문제 링크

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

 

지도 밖으로 나가는 방향의 입력이 주어지지 않고, 무조건 한 방향으로만 갈 수 있으므로 모든 노드는 싸이클에 포함되거나, 싸이클에 연결되어 있다.

싸이클을 이루는 그룹이 몇 개인지 세어주면 된다.

 

내가 푼 풀이는 말 그대로 싸이클의 수를 구하는 코드인데 설명하기가 애매하니 그냥 코드를 보자.

 

더 간단한 방법은 유니온파인드를 이용하면 된다!

 

 

정답 코드

	#include <iostream>
	using namespace std;
	char dtoi[200];
	int p[1001][1001], chk[1001][1001], n, m;
	int dx[] = { 0, 1, 0, -1 }, dy[] = { 1, 0, -1, 0 };
	int dfs(int x, int y, int lev) {
	if (chk[x][y]) return chk[x][y];
	chk[x][y] = lev;
	return chk[x][y] = dfs(x + dx[p[x][y]], y + dy[p[x][y]], lev);
	}
	int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	dtoi['R'] = 0; dtoi['D'] = 1; dtoi['L'] = 2; dtoi['U'] = 3;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	char x;
	cin >> x;
	p[i][j] = dtoi[x];
	}
	}
	int ans = 0, lev = 1;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	int x = dfs(i, j, lev);
	if (x == lev) lev++;
	}
	}
	cout << lev - 1;
	}

view raw 16724.cpp hosted with ❤ by GitHub