백준 16724 피리 부는 사나이, 파이썬
접근
- 방문 기록을 리스트로 기억한다.
- DFS 에 현재 탐색 중인 좌표들이 담긴 큐와 현재 위치를 인자로 받는다.
- 방문마다 방문 기록을 업데이트 해주고 DFS 를 진행한다.
- 방문한 곳을 마주하면 경우는 두 가지이다. Safe zone 으로 나갈 수 있는 경우, 만들어줘야 하는 경우.
사고
제약 조건이 적어 쉽게 접근할 수 있었다. 사이클을 찾으면 그 사이클과 사이클에 들어올 수 있는 모든 경로는 Safe Zone 하나로 도망 가능하다. 이 원칙 하나로 구현하면 큰 어려움 없이 풀 수 있다.
import sys
input = sys.stdin.readline
R, C = map(int, input().split())
m = [list(input().strip()) for j in range(R)]
v = [[False] * C for _ in range(R)]
safezone = 0
dirs = ((-1, 0), (1, 0), (0, -1), (0, 1))
def search(r, c, q):
global safezone
if m[r][c] == 'U':
d = dirs[0]
elif m[r][c] == 'D':
d = dirs[1]
elif m[r][c] == 'L':
d = dirs[2]
else:
d = dirs[3]
v[r][c] = True
if v[r + d[0]][c + d[1]]:
# 방문기록이 있는데 현재 탐색 중인 큐에 있는 곳이라면 Safe Zone 을 설치해야한다.
if (r + d[0], c + d[1]) in q:
safezone += 1
return
else:
# 방문기록이 있는데 탐색 중인 큐에 없다면 연결될
# 새로운 그룹이 Safe Zone 을 갖고 있으며
# 현재 큐도 기존의 Safe Zone 으로 모두 가게 된다.
q.append((r, c))
search(r + d[0], c + d[1], q)
for i in range(R):
for j in range(C):
if not v[i][j]:
search(i, j, [])
print(safezone)
