백준 1189 : 컴백홈 (Python)

본문 링크

import sys
input=sys.stdin.readline

dx=[-1,1,0,0]
dy=[0,0,-1,1]
N,M,K=map(int,input().split())

graph=[ list(input().rstrip()) for i in range(N) ] 

answer=0


def DFS(x,y,count):
    global answer

    if count==K and x==0 and y==M-1:
        answer+=1
    for i in range(4):
        nx=x+dx[i] ; ny=y+dy[i]

        if 0<=nx<N and 0<=ny<M and graph[nx][ny]=='.':
            graph[nx][ny]='T'
            DFS(nx,ny,count+1) 
            graph[nx][ny]='.' #이미왔던 지점은 막아주는대신에 , 끝까지 탐색한후에는 원래되로 되돌려놓는다. 

graph[N-1][0]='T'
DFS(N-1,0,1)
print(answer)

📌 어떻게 접근할 것인가?

그래프 탐색 문제이다. $DFS$ 를 통해 문제를 풀었다.

방문처리는 한번 왔던 지점에 $T$ 라는 벽을 새운후 백트래킹을 사용하여 재귀호출이 끝난뒤에 다시 빈칸으로 만들어주었다.

우리는 오른쪽위로 도착하면서 이동횟수가 K인 경우의 수를 구해야하기때문에
단순히 visit=[ [False] × M for i in range(N) ] 을 통해 방문처리를 해주면
최단경로는 구할수 있지만 모든 경우의 수는 구할수가없다.

따라서 $DFS$ 를 통해 탐색할때마다 이미왔던곳을 벽으로 막아준후 , 오른쪽위로 탐색이 되고 이동횟수가 $K$ 라면 answer 변수에 1을 더한다.
하지만 다른경우도 있을수 있기 때문에 재귀호출이 끝난후 다시 원래되로 되돌려 놓음으로써
다시 다른방향으로 탐색가능하게 해준다.