[백준] 피리 부는 사나이

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

16724번: 피리 부는 사나이

이 문제의 핵심은 DFS를 통해 싸이클을 찾는 것 그리고 다른 싸이클에 포함이 되는지 여부를 찾는 것입니다. 방문되지 않은 위치를 시작으로 DFS로 탐색하다가 방문한 위치를 다시 방문하게 되었을 때 값이 -1이면 새로운 싸이클을 만난 것이고 0보다 큰 값이면 기존에 탐색된 다른 싸이클에 포함되는 것을 의미합니다. 각각의 싸이클에 SAFE ZONE을 설치하면 되므로 싸이클의 수가 곧 정답이 되게 됩니다.

 

import sys

#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n, m = tuple(map(int, input().split()))

board = [
    list(map(str, input().rstrip()))
    for _ in range(n)
]

visited = [
    [0] * m
    for _ in range(n)
]

ans = 0

map = {
    'U': 0,
    'R': 1,
    'D': 2,
    'L': 3
}

group = 0

dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]

def dfs(y, x):
    global group

    visited[y][x] = -1

    dir = map[board[y][x]]

    ny = y + dy[dir]
    nx = x + dx[dir]

    # 새로운 싸이클인 경우
    if visited[ny][nx] == -1:
        group += 1
        visited[y][x] = group
        return group

    # 다른 싸이클을 만나는 경우
    if visited[ny][nx] > 0:
        visited[y][x] = visited[ny][nx]
        return visited[y][x]

    visited[y][x] = dfs(ny, nx)
    return visited[y][x]

for i in range(n):
    for j in range(m):
        if not visited[i][j]:
            dfs(i, j)

print(group)