BOJ 16724 피리 부는 사나이(Python 3)

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

문제 푸는 방식은 간단했지만, 이걸 생각해내는 과정이 참 힘들었던 문제다.

완전 탐색을 돌려서 아직 방문하지 못한 좌표를 만났다면 t+=1을 한 후에, 방문하는 좌표마다 숫자t로 체크해주고, 계속 이동하다가 만약 t로 체크된 좌표와 만났다면 SAFE ZONE을 하나 늘리고 함수를 종료하고(싸이클), 그게 아니라 t`(이전의 t)와 만나면 SAFE ZONE을 늘리지 말고 바로 함수를 종료하는 형식으로 해주었다.

Q) 왜 t`를 만나면 SAFE ZONE을 하나 늘리지 않고, 바로 함수를 나가나요?

(이해를 돕기 위한 그림)

A) 만약 t`가 싸이클이라면 t로 색칠된 좌표에서 이동하다가 결국 t`로 이동해서 t`의 싸이클을 돌 것이고, t`에는 이미 SAFE ZONE이 있기 때문에 추가를 하지 않아도 됩니다. 만약 t`가 싸이클이 아니라면 t`도 t``로 체크를 한 어떤 싸이클로 이동할 것이고, t``에는 이미 SAFE ZONE이 있기 때문에 이 부분 역시 굳이 추가를 하지 않아도 됩니다.

(문제에 어떤 경우에서든 지도 밖으로 나가는 방향의 입력이 주어지지 않는다고 나와있기 때문에 무조건 한 개 이상의 싸이클이 존재함)

재귀 함수를 이용해 문제를 풀었습니다.

코드확인

n,m=map(int,input().split())
D=[list(map(str,[*input()])) for _ in range(n)]
S=[[-1]*m for _ in range(n)]
ans=0;t=0
def a(x,y,k):
    if k=='U':return x-1,y
    if k=='D':return x+1,y
    if k=='L':return x,y-1
    else:return x,y+1
def k(x,y):
    global t,ans
    nx,ny=a(x,y,D[x][y])
    if 0<=nx<n and 0<=ny<m:
        if S[nx][ny]==-1:
            S[nx][ny]=t
            k(nx,ny)
        elif S[nx][ny]==t:
            ans+=1
            return
        else:return
for i in range(n):
    for j in range(m):
        if S[i][j]==-1:
            S[i][j]=t
            k(i,j)
            t+=1
print(ans)