[C++] 백준 16724번: 피리 부는 사나이

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

16724번: 피리 부는 사나이

 

 - 관찰

예제 입력 1

 

여러 경우에 대한 그림을 그려보면 알겠지만, (0, 0)~(N-1, M-1)로 시작하는 순차적인 탐색을 해보면, 이전 탐색과 동선이 겹치는 경우가 있다. 이 경우에는 하나의 '그룹'으로 묶을 수 있으며, 모든 탐색을 마친 뒤 최종적으로 남는 그룹별로 SAFE ZONE을 설치하면 된다.

 

 - 풀이

0. count 변수에 '그룹'의 갯수를 저장하며, 이것을 출력하게 된다.

1. 모든 포지션(x, y)에 대해 순차적으로 탐색을 해야한다.

2. 탐색을 하던 도중, '이번' 탐색 때 방문했던 곳을 또 방문하게 되면 탐색을 중단한다.(싸이클) 이 경우를 '독립적인 탐색'에 성공했다고 칭한다.

3. '이전'에 탐색을 했던 위치는 따로 기억해두어야할 필요가 있다. 이 경우, 탐색을 중단하며 count에 변화를 주어선 안 된다. 이에 따라, 바로 위 2번의 경우, 즉 완벽히 탐색을 마치고 싸이클을 찾은 경우에 count를 1개 증가시켜야한다.

 

이 때 우리는 입력을 받은 info에 '이번 탐색 때 방문한 경우'와 '이전에 탐색을 했을 경우'를 구분지어 각각 0, 1로 저장할 수 있다. 백트래킹을 약간 응용한 방식으로 info의 값을 탐색 전후로 각각 0, 1을 넣음으로써 알맞은 값을 넣을 수 있다. 한 지점에 방문을 하면 더이상 그곳에서 다른 곳으로 탐색을 할 일은 없기 때문에 탐색한 곳의 데이터는 보존 시킬 필요가 없다.

 

#include <iostream>
#include <map>
using namespace std;

map<char, pair<int, int>> dir;
char info[1000][1000];

bool isSearchIndependent(int x, int y) {
	if (info[x][y] == 0) return true;
	else if (info[x][y] == 1) return false;

	char c = info[x][y];
	info[x][y] = 0;	// 이번 탐색 때 방문
	bool res = isSearchIndependent(x + dir[c].first, y + dir[c].second);
	info[x][y] = 1;	// 이전 탐색 때 방문

	return res;
}

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

	dir.insert(make_pair('U', make_pair(-1, 0)));
	dir.insert(make_pair('D', make_pair(1, 0)));
	dir.insert(make_pair('L', make_pair(0, -1)));
	dir.insert(make_pair('R', make_pair(0, 1)));

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

	int i, j;
	for (i = 0; i < N; i++) {
		for (j = 0; j < M; j++) cin >> info[i][j];
	}

	// Solution
	int count = 0;
	for (i = 0; i < N; i++) {
		for (j = 0; j < M; j++) {
			if (isSearchIndependent(i, j)) count++;
		}
	}
	cout << count;
}