[백준 BOJ / Python] 1103번 게임

문제

게임 보드 위의 숫자에 따라 동전을 이동시킬 때, 동전을 움직이는 횟수가 최대가 되도록 하는 문제이다.

보드 위의 숫자는 1부터 9까지 있으며, 해당 칸에서 다음 칸으로 이동할 때 표기된 숫자만큼 한 번에 이동해야 한다.

동전은 상하좌우로 이동할 수 있고, H(구멍) 칸이나 보드 바깥으로 이동되면 게임이 종료된다.

풀이

• 이 문제에서는 깊이 우선 탐색(DFS)과 메모이제이션, 백트래킹을 사용해 풀 수 있다.
• 재귀적으로 DFS를 사용해서 동전이 이동할 수 있는 모든 경로를 탐색한다.

1. 메모이제이션
   
   • DFS 탐색을 하면서 특정 칸에 대한 경로 탐색이 끝나면, 그 칸에서 최대 이동 횟수를 계산한 상태이다.
   • 따라서 중복 탐색을 방지하기 위해, 계산된 값을 메모이제이션을 통해 저장한다.
   • 탐색 도중 이미 계산된 값( dp[x][y] )이 있다면, 즉시 그 값을 반환하면 된다.
2. 무한 루프 방지
   • 탐색 중에 이미 방문한 칸을 다시 방문하게 되면 루프가 발생한 것이다.
   • 이 경우 -1을 출력하고 프로그램을 종료한다.
3. DFS  탐색 과정
   • 다음 칸으로 이동하기 전, 현재 칸에 방문 표시를 한다.
   • 현재 칸에서 board[x][y]에 적힌 숫자만큼 상하좌우로 이동한다.
   • 이동한 위치가 보드를 벗어나거나 구멍('H')에 빠지면 그 경로는 더 이상 탐색하지 않는다.
   • 만약 이동할 수 있다면, 다음 칸으로 이동한 후 최대 이동 횟수를 계산하고, 그 값에 1을 더해 현재 칸의 최대 이동 횟수를 업데이트한다.
   • 백트래킹을 위해 탐색이 끝난 후에는 방문 표시를 해제하여, 다른 경로도 탐색할 수 있게 한다.

Python 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n,m = map(int, input().split())
board = [list(input().strip()) for _ in range(n)]

dp = [[0]*m for _ in range(n)]
visited = [[0]*m for _ in range(n)]

def in_range(x,y):
    return 0<=x<n and 0<=y<m

def dfs(x,y):
    if dp[x][y]:      # 이미 계산된 칸이면 바로 반환
        return dp[x][y]

    if visited[x][y]: # 무한 루프 감지
        print(-1)
        exit()

    visited[x][y] = 1 # 현재 칸 방문 표시
    max_move = 1
    k = int(board[x][y]) # 이동해야 하는 거리
    for dx,dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        nx,ny = x+dx*k, y+dy*k
        if not in_range(nx,ny): # 보드 범위 밖
            continue
        if board[nx][ny] == "H": # 구멍
            continue
        max_move = max(max_move, dfs(nx,ny)+1) # 이동 횟수 업데이트

    visited[x][y] = 0 # 백트래킹: 현재 칸 방문 해제
    dp[x][y] = max_move # 현재 칸까지의 최대 이동 횟수
    return dp[x][y]

print(dfs(0,0))

 

문제출처

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