[Python/파이썬] 백준 1189번 컴백홈

1189번: 컴백홈

 

문제

한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.

      cdef  ...f  ..ef  ..gh  cdeh  cdej  ...f 
      bT..  .T.e  .Td.  .Tfe  bTfg  bTfi  .Tde 
      a...  abcd  abc.  abcd  a...  a.gh  abc. 
거리 :  6     6     6     8     8    10    6

위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것이다.

입력

첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다.

출력

첫 줄에 거리가 K인 가짓수를 출력한다.

코드

def bt(x, y, cnt):
    global ans

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

    if x == 0 and y == c-1 and cnt == k:
        ans += 1
        return

    if cnt > k:  # 거리가 k를 초과하면 더 이상 탐색하지 않음
        return

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < r and 0 <= ny < c and board[nx][ny] == '.':
            board[nx][ny] = 'V'
            bt(nx, ny, cnt+1)
            board[nx][ny] = '.'


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

ans = 0

board[r-1][0] = 'V'  # 출발점 방문 표시
bt(r-1, 0, 1)

print(ans)

처음에는 너비우선탐색으로 해볼까했지만 문제는 최단거리를 구하는 것이 아니라 거리가 k인 모든 경로의 수를 세는 것이었으므로 깊이우선탐색으로 방향을 바꿨다.

 

• 처음 시작점인 (r-1, 0)에서 시작하여 현재 칸에서 상하좌우로 인접한 4칸 중 범위를 넘지않고 칸의 정보가 '.'인 칸을 탐색하는 과정을 재귀적으로 반복한다.
• 집인 (0, c-1)에 거리 k만큼의 경로로 도착하면 전역 변수 ans에 1을 더해주고 리턴한다.
• 우리는 거리가 k인 경로들만 구하는 것이므로 경로의 길이인 cnt가 k를 초과하면 더이상 탐색하지 않는다.