[Python] 백준 1189: 컴백홈

 solved.ac 기분 Silver 1

 백트래킹 문제는 모든 경우의 수를 살펴보는 럭키브루트포스(?)이기 때문에 분기문을 잘 작성해야 시간초과, 메모리 문제에서 벗어날 수 있다. 그러한 기틀을 다지기 위해 재귀를 구성해 중간에 살펴보지 않아도 되는 케이스는 도려낼 수 있는 로직으로 구성해 풀 수 있는 문제이다.

문제

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

      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인 가짓수를 출력한다.

예제 입력 1

3 4 6
....
.T..
....

예제 출력 1

4

 

정답 코드

from collections import deque

R, C, K = map(int, input().split())
board = [list(input()) for _ in range(R)]

d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
visited = [[False] * C for _ in range(R)]
result = 0

def DFS(x, y, dist):

    global R, C, K, board, d, result, visited

    visited[x][y] = True

    if dist > K:
        visited[x][y] = False
        return

    if board[x][y] == 'T':
        return

    

    if x == 0 and y == C-1:
        if dist == K:
            result += 1
        visited[x][y] = False
        return

    for dx, dy in d:
        newX, newY = x + dx, y + dy
        if 0 <= newX < R and 0 <= newY < C:
            if not visited[newX][newY]:
                DFS(newX, newY, dist + 1)

    visited[x][y] = False
                

DFS(R-1, 0, 1)

print(result)

 

 거리가 길어지면, 일부러 돌아가는 경우도 발생할 수 있기에 최단거리를 찾기 보다는 무조건 목적지에 도달하는 경우를 살펴보는 DFS로 문제를 풀었다. 다만 과정의 효율을 위해 탐색 도중 목표하는 거리를 초과하면 탐색을 중단하고, 장애물 T를 만나면 중단한다.