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

1. 문제

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

16724번: 피리 부는 사나이

 

2. 알고리즘 분류

• 자료 구조
• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색
• 분리 집합

 

3. 소스코드

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

unordered_map<char, pair<int, int>> dir;
int N, M;
char map[1003][1003];

// 해당 맵 포인트가 탐색이 되었는지 여부 확인
bool is_search(int y, int x)
{
	if (map[y][x] == 0) return false;	// 현재 지나가고 있는 길에 도착했을 경우, False 반환
	else if (map[y][x] == 1) return true;	// 이미 탐색이 완료된 길인 경우, True 반환
	
	char val = map[y][x];
	map[y][x] = 0;	// 지나가고 있는 길 표시
	bool ret = is_search(y + dir[val].first, x + dir[val].second);	// 다음 지점으로 계속 이동
	map[y][x] = 1;  // 탐색 완료되었다는 표시

	return ret;
}

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

	// 알파벳에 따른 이동 방향 설정
	dir['U'] = { -1, 0 };
	dir['D'] = { 1, 0 };
	dir['L'] = { 0, -1 };
	dir['R'] = { 0, 1 };

	// N : 지도의 행의 수, M : 지도의 열의 수 입력
	cin >> N >> M;

	// 지도의 정보 입력
	for (int y = 0; y < N; y++)
		for (int x = 0; x < M; x++)
			cin >> map[y][x];

	int cnt = 0;

	// 모든 지점 탐색
	for (int y = 0; y < N; y++)
		for (int x = 0; x < M; x++)
			if (!is_search(y, x)) cnt++;	// 탐색이 되지않았다면 Count 1 증가

	// 정답 출력
	cout << cnt;

	return 0;
}

 

4. 유용한 알고리즘

 1) DFS(깊이 우선 탐색)

• 재귀로 들어가기 전에, map[y][x]에 0을 넣어주게 되면, 현재 DFS를 하면서 해당 좌표가 탐색 중이라는 것을 표기할 수 있다.
• 재귀로 들어가고 나온 후에, map[y][x]에 1을 넣어주게 되면, 탐색 다 끝나고 완료되었다는 것을 표기할 수 있다. 

bool is_search(int y, int x)
{
	if (map[y][x] == 0) return false;	// 현재 지나가고 있는 길에 도착했을 경우, False 반환
	else if (map[y][x] == 1) return true;	// 이미 탐색이 완료된 길인 경우, True 반환
	
	char val = map[y][x];
	map[y][x] = 0;	// 지나가고 있는 길 표시
	bool ret = is_search(y + dir[val].first, x + dir[val].second);	// 다음 지점으로 계속 이동
	map[y][x] = 1;  // 탐색 완료되었다는 표시

	return ret;
}