[BOJ/Python] 1189 : 컴백홈

👉 문제 링크

👉 전체 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

r,c,k = map(int, input().split())
graph = [list(input()) for _ in range(r)]

dx = [1,-1,0,0]
dy = [0,0,1,-1]

def dfs(x,y,d):
    global cnt
    visited[x][y] = True
    if d == k and x == 0 and y == c-1:
        cnt += 1
        return

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0<=nx<r and 0<=ny<c and graph[nx][ny] != 'T' and not visited[nx][ny]:
            dfs(nx,ny,d+1)
            visited[nx][ny] = False 

visited = [[False]*c for _ in range(r)]
cnt = 0
dfs(r-1,0,1)
print(cnt)

👉 풀이

경우의 수를 계산하는 문제이므로 방문처리를 해당 경로마다 해주어야 한다.
따라서, 탐색이 끝나면 방문처리를 다시 False로 바꿔주어야 한다.

왼쪽 아래에서 오른쪽 위로 탐색해야 하기 때문에
거리가 k, 현재 위치가 오른쪽 위 즉, 0,c-1일 때 카운팅 해준다. (코드에서 cnt 변수)