[DFS / 파이썬] 백준 16724번 : 피리 부는 사나이 / 골드 2

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

16724번: 피리 부는 사나이

x_lim, y_lim = map(int, input().split())
table = []
for _ in range(x_lim):
    table.append([x for x in input()])

group = [[-1 for _ in range(y_lim)] for _ in range(x_lim)]

direction = ['L', 'R', 'U', 'D']
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def move(x, y, idx):
    global answer
    if group[x][y] != -1:
        if group[x][y] == idx:
            answer += 1
        return

    group[x][y] = idx
    i = direction.index(table[x][y])
    move(x + dx[i], y + dy[i], idx)

idx = 0
answer = 0
for i in range(x_lim):
    for j in range(y_lim):
        move(i, j, idx)
        idx += 1

print(answer)

dfs로 탐색하며 싸이클 형성 여부를 살핀다.

 

그럼 언제 answer에 1을 더해주는가?

이미 방문했던 곳에 도착했을 때 마침 group[x][y] == idx일 경우일 때다. 즉 최초로 싸이클이 발견되는 순간이다. 

방문했던 곳에 도착하더라도 group[x][y] != idx이면 이미 형성된 싸이클에 진입하는 경우이므로 answer를 더해주면 안된다.