BOJ 16724번: 피리 부는 사나이

문제

문제 바로가기> BOJ 16724번: 피리 부는 사나이

16724번: 피리 부는 사나이

 

풀이

dfs 탐색을 통해 이동을 진행하다가, 해당 턴에서 이미 방문했던 곳으로 돌아오는 경우, 

SAFE ZONE이 필요한 것이므로 ans를 1증가해주었다!

 

#include<iostream>
#include<string>
#define MAX 1001
using namespace std;

int N, M, ans=0;
char map[MAX][MAX];
int visited[MAX][MAX];

void input() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		string line; cin >> line;
		for (int j = 0; j < M; j++) map[i][j] = line[j];
	}
}

void dfs(int y, int x, int n) {
	visited[y][x] = n;
	
	int ny=y, nx=x;
	if (map[y][x] == 'U') ny--;
	else if (map[y][x] == 'D') ny++;
	else if (map[y][x] == 'L') nx--;
	else if (map[y][x] == 'R') nx++;
	
	if(visited[ny][nx]==0) dfs(ny, nx, n);
	else if (visited[ny][nx] == n) ans++;
}

void solution() {
	int n = 1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (visited[i][j]) continue;
			dfs(i, j, n++);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	input();
	solution();
	cout << ans;
}