[Gold II] 게임 - 1103

문제 링크

성능 요약

메모리: 34984 KB, 시간: 56 ms

분류

다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 깊이 우선 탐색

문제 설명

형택이는 1부터 9까지의 숫자와, 구멍이 있는 직사각형 보드에서 재밌는 게임을 한다.

일단 보드의 가장 왼쪽 위에 동전을 하나 올려놓는다. 그다음에 다음과 같이 동전을 움직인다.

1. 동전이 있는 곳에 쓰여 있는 숫자 X를 본다.
2. 위, 아래, 왼쪽, 오른쪽 방향 중에 한가지를 고른다.
3. 동전을 위에서 고른 방향으로 X만큼 움직인다. 이때, 중간에 있는 구멍은 무시한다.

만약 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료된다. 형택이는 이 재밌는 게임을 되도록이면 오래 하고 싶다.

보드의 상태가 주어졌을 때, 형택이가 최대 몇 번 동전을 움직일 수 있는지 구하는 프로그램을 작성하시오.

입력

줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 형택이가 동전을 무한번 움직일 수 있다면 -1을 출력한다.

---

문제 풀이

문제 분석

이 문제는 N x M 크기의 직사각형 보드에서 동전을 움직여 최대 몇 번 이동할 수 있는지 구하는 문제입니다. 보드 칸에는 1부터 9까지의 숫자 또는 'H' (구멍)이 쓰여 있습니다.

1. 게임 시작: 동전은 보드의 가장 왼쪽 위 (0,0) 칸에서 시작합니다.
2. 이동 규칙:
   • 현재 동전이 있는 칸의 숫자 X를 확인합니다.
   • 상, 하, 좌, 우 네 방향 중 하나를 선택합니다.
   • 선택한 방향으로 X만큼 동전을 움직입니다. 이때, 중간에 있는 구멍은 무시합니다.
3. 게임 종료: 동전이 보드의 경계를 벗어나거나, 'H' (구멍) 칸에 도착하면 게임이 종료됩니다.
4. 목표: 동전을 최대한 오래 움직였을 때의 최대 이동 횟수를 구해야 합니다. 만약 동전을 무한히 움직일 수 있다면 -1을 출력합니다.
5. 입력: 보드의 세로 크기 N과 가로 크기 M (각각 50 이하), 그리고 N줄에 걸쳐 보드의 상태 (숫자 또는 'H')가 주어집니다. 시작 칸 (0,0)은 'H'가 아닙니다.
6. 출력: 최대 이동 횟수 또는 -1.

접근 방법

이 문제는 보드 위에서 가능한 경로를 탐색하여 최대 이동 횟수를 찾아야 하며, 무한히 움직일 수 있는 경우(사이클)도 처리해야 합니다. 이러한 특성을 고려할 때, 다이나믹 프로그래밍(Dynamic Programming, DP)과 깊이 우선 탐색(Depth First Search, DFS)을 결합한 방식이 가장 적합합니다.

1. DP 상태 정의: dp[r][c]는 (r, c) 위치에서 시작했을 때 얻을 수 있는 최대 이동 횟수를 저장합니다. 아직 계산되지 않은 경우 0으로 초기화합니다.
2. DFS 탐색: DFS(r, c) 함수는 (r, c)에서 시작하여 가능한 모든 경로를 탐색하고, 각 경로에서 얻을 수 있는 이동 횟수를 계산하여 dp[r][c]에 저장합니다.
3. 메모이제이션: DFS(r, c)가 호출되었을 때, 이미 dp[r][c] 값이 계산되어 있다면 (0이 아니라면) 바로 해당 값을 반환하여 중복 계산을 피합니다.
4. 사이클 (무한 이동) 감지: 무한히 움직일 수 있는 경우는 게임 경로가 자기 자신을 포함하여 반복되는 "사이클"을 형성할 때 발생합니다. 이를 감지하기 위해 visited[r][c] 배열을 사용합니다.
   • DFS(r, c)가 시작될 때 visited[r][c] = True로 설정합니다.
   • DFS 도중 다음 이동할 위치 (nr, nc)가 현재 DFS 호출 스택에 이미 존재하는 visited[nr][nc] == True 상태라면, 사이클이 발생한 것입니다. 이 경우 float("inf")를 반환하여 무한 이동 가능성을 상위 호출로 전파합니다.
   • DFS(r, c)가 모든 탐색을 마치고 반환하기 직전에 visited[r][c] = False로 설정합니다. 이는 다른 경로가 (r, c)를 방문할 수 있도록 상태를 초기화하는 "백트래킹" 과정입니다.
5. 재귀 깊이 설정: N, M이 최대 50이므로, 최악의 경우 재귀 호출 깊이가 N*M에 이를 수 있습니다. Python의 기본 재귀 깊이 제한을 늘려주어야 합니다.

구현 설명

1. 초기 설정 및 보드 입력

• sys.setrecursionlimit(10**7): Python의 기본 재귀 깊이 제한이 충분하지 않을 수 있으므로, 제한을 10^7로 크게 늘립니다.
• N, M을 입력받고, board를 N x M 크기의 2차원 리스트로 저장합니다. 각 칸은 문자열('1'~'9', 'H')로 저장됩니다.
• dp = [[0] * m for _ in range(n)]: 각 칸 (r, c)에서 시작하여 얻을 수 있는 최대 이동 횟수를 저장할 DP 테이블입니다. 0은 아직 계산되지 않았음을 의미합니다.
• visited = [[False] * m for _ in range(n)]: 현재 DFS 경로에서 특정 칸을 방문했는지 여부를 표시하는 테이블입니다. 사이클 감지에 사용됩니다.
• directions = [(1,0),(-1,0),(0,1),(0,-1)]: 상, 하, 좌, 우 네 방향을 정의합니다. (dr, dc) 형태로 저장됩니다.

2. DFS 함수 정의 및 메모이제이션

• def DFS(x, y): 함수는 현재 동전이 (x, y) 위치에 있을 때부터 얻을 수 있는 최대 이동 횟수를 반환합니다.
• if dp[x][y]: return dp[x][y]
  • 만약 (x, y) 위치에 대한 dp 값이 이미 계산되어 있다면 (0이 아니라면), 그 값을 바로 반환하여 중복 계산을 방지합니다. 이것이 메모이제이션입니다.
• visited[x][y] = True: 현재 (x, y) 칸을 현재 DFS 경로에서 방문했음을 표시합니다.
• move = int(board[x][y]): 현재 칸의 숫자 X를 가져옵니다.
• max_cnt = 0: (x, y)에서 시작하여 얻을 수 있는 최대 추가 이동 횟수를 저장할 변수를 초기화합니다.

3. 다음 이동 경로 탐색 및 사이클 감지

• for dx, dy in directions:: 네 방향 각각에 대해 다음 이동할 칸을 탐색합니다.
• sx = x + dx * move
• sy = y + dy * move: X만큼 이동한 다음 칸의 좌표 (sx, sy)를 계산합니다.
• if not (0<=sx<n and 0<=sy<m): continue: (sx, sy)가 보드 범위를 벗어나면 게임 종료. 이 경로는 무시하고 다음 방향 탐색.
• if board[sx][sy] == "H": continue: (sx, sy)가 구멍이면 게임 종료. 이 경로는 무시하고 다음 방향 탐색.
• if visited[sx][sy]: return float("inf"): 만약 (sx, sy)가 현재 DFS 경로에 이미 포함되어 있다면(즉, visited[sx][sy]가 True라면), 사이클이 발생한 것입니다. 이는 무한히 이동할 수 있음을 의미하므로 float("inf")를 반환하여 이 정보를 전파합니다.
• result = DFS(sx, sy): 다음 칸 (sx, sy)에서 시작하는 최대 이동 횟수를 재귀적으로 호출하여 가져옵니다.
• if result == float("inf"): return result: 만약 재귀 호출 결과가 float("inf")라면, 이 경로도 무한 이동이 가능하므로 float("inf")를 즉시 반환하여 전파합니다.
• max_cnt = max(max_cnt, result): 현재 칸 (x,y)에서 갈 수 있는 모든 유효한 다음 칸들 중 가장 많은 추가 이동 횟수를 max_cnt에 업데이트합니다.

4. DP 테이블 업데이트 및 결과 반환 (백트래킹)

• visited[x][y] = False: (x, y) 칸에 대한 DFS 탐색이 완료되었으므로, visited 상태를 False로 되돌립니다. 이는 백트래킹 과정으로, 다른 DFS 경로가 (x, y)를 다시 방문할 수 있도록 합니다.
• dp[x][y] = max_cnt + 1: (x, y)에서 시작하는 총 이동 횟수는 다음 칸에서 얻을 수 있는 최대 이동 횟수 (max_cnt)에 현재 (x, y)에서 (sx, sy)로 이동하는 1번의 이동을 더한 값입니다. 이 값을 dp[x][y]에 저장합니다.
• return dp[x][y]: 계산된 최대 이동 횟수를 반환합니다.

5. 최종 결과 출력

• result = DFS(0,0): 게임은 (0,0)에서 시작하므로, DFS(0,0)을 호출하여 최종 결과를 얻습니다.
• if result == float("inf"): print(-1): 만약 result가 무한대라면 -1을 출력합니다.
• else: print(result): 그렇지 않다면 계산된 최대 이동 횟수를 출력합니다.

⏱복잡도 분석

• 시간 복잡도: O(N * M)

  • DFS 함수는 각 (x, y) 위치에 대해 한 번만 dp[x][y] 값을 계산합니다. (메모이제이션 덕분)
  • 각 DFS(x, y) 호출 내부에서는 상수로 4방향을 탐색하고, 각 방향에 대해 몇 가지 조건 검사와 재귀 호출이 이루어집니다. 이 작업은 N*M번의 DFS 호출 각각에 대해 상수 시간에 수행됩니다.
  • 따라서 전체 시간 복잡도는 보드 칸의 개수에 비례하는 O(N * M)이 됩니다. N, M이 각각 50이므로, 50 * 50 = 2500번의 DFS 호출이 최대로 일어납니다.

• 공간 복잡도: O(N * M)

  • board: 보드 상태를 저장하는 데 O(N * M) 공간이 필요합니다.
  • dp: 메모이제이션 테이블로 O(N * M) 공간이 필요합니다.
  • visited: 현재 DFS 경로를 추적하는 데 O(N * M) 공간이 필요합니다.
  • 재귀 스택: 최악의 경우 (사이클 없이 모든 칸을 한 번씩 방문하는 긴 경로) 재귀 호출 깊이가 N * M까지 갈 수 있으므로 O(N * M) 공간이 필요합니다.
  • 따라서 전체 공간 복잡도는 O(N * M)입니다.

핵심 포인트

1. 다이나믹 프로그래밍 (메모이제이션): 각 칸 (x,y)에서 시작했을 때의 최대 이동 횟수를 dp[x][y]에 저장하여, 동일한 상태에 대한 계산을 반복하지 않도록 합니다. 이는 시간 복잡도를 O(N*M)으로 유지하는 핵심 요소입니다.
2. 깊이 우선 탐색 (DFS): 재귀적인 DFS를 사용하여 보드의 모든 가능한 이동 경로를 탐색합니다. 각 칸에서 네 방향으로 X만큼 이동하는 규칙을 구현하고, 보드 경계 및 'H' 칸에 대한 종료 조건을 처리합니다.
3. 사이클 감지 (무한 이동 처리): visited 배열을 사용하여 현재 DFS 호출 스택에 있는 노드를 표시합니다. 만약 DFS가 이미 visited 상태인 노드를 다시 방문하려고 하면, 이는 사이클이 발생했음을 의미하며, 무한히 이동할 수 있다는 뜻이므로 float("inf")를 반환하여 이를 전파합니다. DFS 함수가 리턴될 때 visited 배열을 False로 되돌리는 백트래킹이 중요합니다.

풀이 코드

import sys
from collections import deque
sys.setrecursionlimit(10**7)

input = sys.stdin.readline

n,m = map(int,input().split())

board = []

for i in range(n):
    board.append(list(input().strip()))

dp = [[0] * m for i in range(n)]
visited = [[False] * m for i in range(n)]
directions = [(1,0),(-1,0),(0,1),(0,-1)]

def DFS(x,y):
    if dp[x][y]:
        return dp[x][y]

    visited[x][y] = True
    move = int(board[x][y])
    max_cnt = 0

    for dx, dy in directions:
        sx = x+dx * move
        sy = y+dy * move

        if not (0<=sx<n and 0<=sy<m):
            continue
        if board[sx][sy] == "H":
            continue
        if visited[sx][sy]:
            return float("inf")

        result = DFS(sx, sy)
        if result == float("inf"):
            return result

        max_cnt = max(max_cnt, result)

    visited[x][y] = False
    dp[x][y] = max_cnt + 1
    return dp[x][y]

result = DFS(0,0)

if result == float("inf"):
    print(-1)
else:
    print(result)