[Python] 백준/BOJ 1189번: 컴백홈 (Silver 1)

💻 Problem

문제 보러 가기

 

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

      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인 가짓수를 구하는 것이다.

 

💡 Approach

처음에는 문제를 보고 자연스럽게 bfs로 풀었다.

하지만 bfs로 풀다 보니 방문 처리에 문제가 생겼다.

cdef bT.. a...

..ef .T.e abcd

문제의 예제에서 두 가지만 가져와봤다.

이 경우 처음에 e를 지나치면서 방문 처리를 했기에 그 다음 방법에서는 e를 못 가게 된다.

방문 처리를 다 따로 하기엔 너무 복잡하고 ..

 

그래서 dfs로 푸는 걸로 바꿨다.

dfs는 재귀의 형태이기 때문에 재귀 호출 전에 방문 처리를 True로 하고 재귀 호출 후에 다시 방문 처리를 False로 하면서 문제가 해결됐다.

 

내 코드의 경우에는 도착 지점에 일찍 도달했을 대 조기 종료하고 있다.

가지치기를 더 하고 싶으면 이런 방법도 있다.

• 남은 이동 거리로 도착 가능성 없을 때 가지치기
  • 맨해튼 거리로 계산해서 남은 칸 수가 너무 적거나 너무 많으면 더 탐색할 필요 X
• 사전에 지나갈 수 있는 칸 개수가 K보다 작으면 탐색 안 하기

 

✏️ Solution

import sys
from collections import deque
input = sys.stdin.readline

def dfs(y, x, d):
    global case

    if (y, x) == (0, C - 1):
        if d == K:
            case += 1
        return
    
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]

        if (0 <= ny < R) and (0 <= nx < C) and not visited[ny][nx]:
            if board[ny][nx] == '.':
                visited[ny][nx] = True
                dfs(ny, nx, d + 1)
                visited[ny][nx] = False

R, C, K = map(int, input().split())
board = [list(input().rstrip()) for _ in range(R)]
visited = [[False] * C for _ in range(R)]
visited[R - 1][0] = True
case = 0

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

dfs(R - 1, 0, 1)
print(case)

dfs의 시간복잡도는 V+E지만 백트래킹 시간복잡도는 일반적으로 n개 중 m개를 뽑을 때, 중복 허용이면 n^m, 중복 없이면 n!라고 한다.

하지만 이 문제는 조합/순열 문제이기 때문에 그대로 적용되지 않는다.

 

가능한 경로는 방문한 칸을 다시 방문하지 않으므로 모든 경로는 최대 R*C 깊이까지만 탐색한다.

각 칸에서 최대 4방향 이동하므로 시간복잡도는 4^(R*C)이다.