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

문제 링크: https://www.acmicpc.net/problem/16724

16724번: 피리 부는 사나이

1. 주의할 점

- DP(메모아이제이션) + DFS로 해결한다

 

2. 구현

- Check[][] 배열을 -1로 초기화 시킨다

- 2중 For문을 돌며 Check[][]값이 -1이면 DFS()를 수행하며, 끝나면 Cnt++를 해준다

- DFS(y,x)에서는 Check[y][x]값이 -1이 아니면 Check[y][x]값을 반환한다

- -1이라면 Check[y][x]값을 Cnt로 갱신후, 해당 Arr[][]에 적힌 문자대로 수행하며 최종적으로 Check[y][x]에는 반환받은 값을 대입한다

- 위의 빨간색을 수행하는 이유: Cnt로 갱신 안하고 계속 다음 좌표의 DFS를 수행하면 Cycle이 무한으로 돌아서 아무것도 갱신되지 않는다

- 모든 For문 탐색이 끝난 후, Set을 통해 Check[][]에 사용된 번호의 개수를 출력한다

 

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
int row, col, result = 0, cnt = 1;
char arr[1000][1000];
int check[1000][1000];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };

int dfs(int y, int x) {
	if (check[y][x] != -1) return check[y][x];
	int ret = check[y][x];
	check[y][x] = cnt;
	int dir;
	if (arr[y][x] == 'U') dir = 0;
	else if (arr[y][x] == 'R') dir = 1;
	else if (arr[y][x] == 'D') dir = 2;
	else if (arr[y][x] == 'L') dir = 3;
	int nx = x + dx[dir];
	int ny = y + dy[dir];
	ret = dfs(ny, nx);
	check[y][x] = ret;
	return check[y][x];
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> row >> col;
	for(int i=0;i<row;i++)
		for (int j = 0; j < col; j++) {
			cin >> arr[i][j];
			check[i][j] = -1;
		}
	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++) {
			if (check[i][j] == -1) {
				dfs(i, j);
				cnt++;
			}
		}
	set<int> s;
	for (int i = 0; i < row; i++) 
		for (int j = 0; j < col; j++) 
			s.insert(check[i][j]);			
	cout << s.size();
	system("pause");
	return 0;
}