[Python] boj no. 16724 : 피리 부는 사나이

Problem

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

Idea

‘SAFE ZONE’은 다음과 같은 경우에 하나씩 필요하다.

1. 그래프 내에 사이클이 존재할 경우.
2. 배열 외부로 향하는 간선이 존재하는 경우.

배열을 순회하면서 모든 정점에 대해 순차적으로 탐색하며 다음과 같은 기준을 통해 세이프 존을 추가한다.

1. 한번도 방문하지 않은 정점에 대해서만 탐색을 시작한다.
2. 현재 탐색에서 방문한 정점으로 이동하는 경우, 사이클이 존재하므로 세이프 존을 추가한다.
3. 이전에 방문한 적이 있던 정점으로 이동하는 경우, 세이프 존이 존재하는 정점 집합과 합쳐지는 것으로 간주하고 세이프 존을 추가하지 않는다.
4. 배열의 외부로 이동하려는 경우, 세이프 존을 추가한다.

Code

import sys

def dfs(y, x, c):
    cy, cx = y, x
    
    while True:
        visited[cy][cx] = c
        ny, nx = cy + dy[direction[graph[cy][cx]]], cx + dx[direction[graph[cy][cx]]]
        if 0 <= ny < N and 0 <= nx < M:
            if visited[ny][nx] == 0:
                cy, cx = ny, nx
            elif visited[ny][nx] == c:
                flag = 1
                break
            else:
                flag = 0
                break
        else:
            flag = 1
            break     
        
    return flag
            
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(N)]
visited = [[0 for _ in range(M)] for _ in range(N)]

dy = [-1, 1, 0, 0]
dx = [0, 0, -1 ,1]
direction = {'U' : 0, 'D' : 1, 'L' : 2, 'R' : 3}

sol = 0
cnt = 1
for i in range(N):
    for j in range(M):
        if visited[i][j] == 0:
            sol += dfs(i, j, cnt)
            cnt += 1
            
print(sol)

Comment