[BOJ] 1103 - 게임 (Python)

 

 

아이디어

 

동적 계획법과 DFS로 동전을 더 이동할 수 없는 곳에서부터 이동할 수 있는 최대 횟수를 구해 나간다.

 

 

풀이

 

람다식으로 입력으로 주어지는 문자열에서 H는 0으로, 나머지는 정수형으로 바꾼 리스트를 리스트 board에 저장한다.

각 칸의 동전 최대 이동 횟수를 저장하는 2차원 리스트 dp와 각 칸의 방문 여부를 표시하는 2차원 리스트 visited를 만든다.

가장 왼쪽 위칸의 행, 열, 이동 칸 수를 인자로 함수 dfs를 호출한다.

 

함수 dfs에서는 현재 칸을 이미 방문하여 최대 이동 횟수가 dp에 저장되어 있으면 해당 값을 반환하여 종료한다.

dp에 저장되어 있지 않으면 최대 이동 횟수를 저장하는 move에 1을 저장하고, visited에 방문 표시를 한다.

 

보드의 범위를 벗어나지 않고 이동할 수 있는 칸을 이미 방문했다면 동전을 무한번 움직일 수 있으므로 -1을 반환한다.

방문한 적이 없고 구멍이 아니라면 함수 dfs를 재귀 호출한 후 temp에 반환값을 저장한다.

반환값이 -1이면 break문으로 빠져 나오고, move보다 더 크거나 같다면 move를 temp보다 1 더 큰 값으로 갱신한다.

다음 방문을 위해 visited에서 방문 표시를 지우고, dp에 move에 저장된 동전의 최대 이동 횟수를 저장한다.

 

import sys

sys.setrecursionlimit(2502)
input = sys.stdin.readline

delta = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def dfs(i, j, k):
    if dp[i][j]:
        return dp[i][j]
    move = 1
    visited[i][j] = 1
    for di, dj in delta:
        ni, nj = i+di*k, j+dj*k
        if N > ni >= 0 and M > nj >= 0:
            if visited[ni][nj]:
                return -1
            elif board[ni][nj]:
                temp = dfs(ni, nj, board[ni][nj])
                if temp < 0:
                    move = -1
                    break
                elif temp >= move:
                    move = temp+1
    visited[i][j] = 0
    dp[i][j] = move
    return dp[i][j]

N, M = map(int, input().split())
board = [list(map(lambda x: 0 if x == 'H' else int(x), [*input().rstrip()])) for _ in range(N)]
dp = [[0]*M for _ in range(N)]
visited = [[0]*M for _ in range(N)]
dfs(0, 0, board[0][0])
print(dp[0][0])