[Python] boj no. 1103 : 게임

Problem

https://www.acmicpc.net/problem/1103

Idea

dfs를 이용해 가능한 모든 경로를 탐색했다. 동전의 최대 이동 횟수만 구하면 되므로, dp 리스트를 선언하여 각 인덱스까지 도달하는 최대 이동 횟수를 저장하고 해당 경로의 이동 횟수가 dp보다 작을 경우 탐색을 중지하도록 했다(pruning). 또한 경로 진행 중 이미 방문한 인덱스로 또 다시 방문할 경우 사이클이 존재하는 것으로 동전이 무한히 움직일 수 있다. 이를 염두하며 dfs를 구현했다.

1. board의 크기를 넘어가거나 구멍인 인덱스는 탐색하지 않음.
2. 현재 경로에서 방문했던 인덱스로 또 다시 방문할 경우, 사이클이 발생한 것으로 판단하고 모든 탐색을 중지함.
3. 현재 경로에서 방문한 적이 없고 인덱스의 dp가 현재 이동 회숫보다 작을 경우 탐색함.
4. dfs 종료 시 경로 상의 현재 인덱스에서 가능한 최대 이동 횟수를 리턴.

재귀를 통해 dfs를 구현했으니 최대 재귀를 설정할 필요가 있다. N, M <= 50 이고 네 방향으로 탐색할 수 있으니 이론 상의 최대 재귀 횟수는 50 * 50 * 4 = 10^5이 되겠지만 가지치기를 통해 경로의 수가 줄어들 것이므로 실제 최대 재귀는 그보다 적을 것이다.

Code

import sys
sys.setrecursionlimit(10 ** 5)

def dfs(y, x, c):
    visited[y][x] = True
    dp[y][x] = c
    
    c += 1
    ans = dp[y][x]
    for i in range(4):
        weight = int(board[y][x])
        ny, nx = y + dy[i]*weight, x + dx[i]*weight
                
        if 0 <= ny < N and 0 <= nx < M and board[ny][nx] != 'H':
            if visited[ny][nx] == True:
                return -1
            elif visited[ny][nx] == False and dp[ny][nx] < c:
                temp = dfs(ny, nx, c)
                if temp == -1:
                    ans = -1
                    break
                else:
                    ans = max(ans, temp)
                    
    visited[y][x] = False
    
    return ans

input = sys.stdin.readline

N, M = map(int, input().split())
board = [list(input().rstrip()) for _ in range(N)]

dp = [[-1 for _ in range(M)] for _ in range(N)]
visited = [[False for _ in range(M)] for _ in range(N)]
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

sol = dfs(0, 0, 1)
print(sol)

Comment

visited 리스트를 관리하는 것에 있어 좀 헤맸다. 한 경로에 대한 깊이 우선 탐색이 끝난 후 백트래킹하는 과정에서 visited가 원상 복귀되지 않으면 다른 경로에 대한 탐색에서 오류가 발생할 수 있기 때문이다. dfs 종료 시 visited를 False로 수정하는 아이디어를 떠올리기까지 시간이 걸렸다.