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

문제

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

설명

주어진 지도의 사이클의 개수를 찾는 문제이다. 각 노드에 대하여 DFS를 수행하여 사이클을 찾는다. DFS를 수행 후 리턴될 때 visited[i][j]을 -1로 설정한다. 이는 추후 DFS를 수행 시 이미 생성된 사이클의 노드에 접근하지 못하게 하는 역할을 한다.

 

범위 밖으로 나가는 입력은 주어지지 않으므로 잘못된 배열 인덱스를 참조하는 경우는 고려하지 않아도 된다.

코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<string> board;
int visited[1000][1000]; // 1: 방문, -1: 방문 완료
int cnt = 0;

void dfs(int x, int y) {
	visited[x][y] = 1;
	
	char cur = board[x][y];
	if (cur == 'U') {
		int nx = x - 1;
		int ny = y;

		if (visited[nx][ny] == 0)
			dfs(nx, ny);
		else if (visited[nx][ny] == 1)
			cnt++;
	}
	else if (cur == 'D') {
		int nx = x + 1;
		int ny = y;

		if (visited[nx][ny] == 0)
			dfs(nx, ny);
		else if (visited[nx][ny] == 1)
			cnt++;
	}
	else if (cur == 'L') {
		int nx = x;
		int ny = y - 1;

		if (visited[nx][ny] == 0)
			dfs(nx, ny);
		else if (visited[nx][ny] == 1)
			cnt++;
	}
	else if (cur == 'R') {
		int nx = x;
		int ny = y + 1;

		if (visited[nx][ny] == 0)
			dfs(nx, ny);
		else if (visited[nx][ny] == 1)
			cnt++;
	}

	visited[x][y] = -1;
}

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

	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		board.push_back(s);
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (visited[i][j] == 0) {
				dfs(i, j);
			}
		}
	}

	cout << cnt;
}