[BOJ 16724 // C++] 피리 부는 사나이

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 16724번 문제인 피리 부는 사나이이다.
문제는 아래 링크를 확인하자.

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

16724번: 피리 부는 사나이

각 칸에서 주어진 방향으로 이동하다보면 문제 조건에 따라 어느 순간 같은 장소를 빙빙 돌게 될 수밖에 없다는 것을 관찰하자. (지도의 크기가 유한하고, 지도 밖으로 나가는 방향의 입력은 주어지지 않기 때문이다)

 

따라서, 이 문제는 그러한 사이클이 몇개 존재하는지 찾는 문제로 바꿔서 생각할 수 있다. 각 사이클에는 최소한 하나의 세이프존이 설치되어야 하고, 사이클 위가 아닌 곳에서는 이동을 반복하면 사이클로 올 수밖에 없기 때문이다.

 

이미 한번 조사했던 칸을 다시 조사하기 시작하면 이전에 발견한 사이클 위로 이동하게 된다는 점을 이용하여 중복된 탐색을 줄이자.

 

아래는 제출한 소스코드이다.

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

int ans = 0;
short visited[1000][1000];
string board[1000];

void cycle(int r, int c) {
	vector<pair<int, int>> vec;
	while (!visited[r][c]) {
		visited[r][c] = 2;
		vec.emplace_back(make_pair(r, c));
		char x = board[r][c];
		if (x == 'D') r++;
		else if (x == 'U') r--;
		else if (x == 'L') c--;
		else c++;
	}
	if (visited[r][c] == 2) ans++;
	for (auto p : vec) visited[p.first][p.second] = 1;
}

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

	int R, C; cin >> R >> C;
	for (int r = 0; r < R; r++) cin >> board[r];

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (visited[r][c]) continue;
			cycle(r, c);
		}
	}

	cout << ans;
}