[게임/G2/Python3]

1103번 게임 G2

 

문제
형택이는 1부터 9까지의 숫자와, 구멍이 있는 직사각형 보드에서 재밌는 게임을 한다. 일단 보드의 가장 왼쪽 위에 동전을 하나 올려놓는다. 그다음에 다음과 같이 동전을 움직인다. 동전이 있는 곳에 쓰여 있는 숫자 X를 본다. 위, 아래, 왼쪽, 오른쪽 방향 중에 한 가지를 고른다. 동전을 위에서 고른 방향으로 X만큼 움직인다. 이때, 중간에 있는 구멍은 무시한다. 만약 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료된다. 형택이는 이 재밌는 게임을 되도록이면 오래 하고 싶다. 보드의 상태가 주어졌을 때, 형택이가 최대 몇 번 동전을 움직일 수 있는지 구하는 프로그램을 작성하시오.

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

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

 

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

 

dfs에서는 현재 위치에서 이동 가능한 정점을 재귀 탐색하며, 다시 해당 정점들의 결과를 다시 재확인 한다.

 

2차원 dp 배열에는 각 정점에서 이동 가능한 횟수의 최댓값을 저장한다.

 

이동 가능한 횟수가 0인 경우는 'H'가 유일하다.

이동 가능한 횟수가 1인 경우에는 어디에도 방문할 수 없거나, 방문 가능한 정점이 'H' 뿐인 경우이다.

 

사이클이 생기는 것을 확인하기 위해, dfs에 진입 시 dp의 값을 -1로 변경한다. dfs를 돌리던 중 -1로 된 정점에 방문이 가능하다면 무한히 이동 가능하기 때문이다.

 

dfs의 실행 내용은 다음과 같다.

1. 현재 위치가 H이면 이동 가능 횟수를 0으로 변경 후 돌아간다.

2. 방문 가능한 정점이 없다면, 이동 가능횟수를 1로 변경 후 돌아간다. (보드의 바깥으로 나가는 것도 1이다)

3. 방문하지 않는 정점을 방문한다.

4. 방문 가능한 정점의 이동 가능 횟수가 -1(사이클)이라면, 이 정점도 -1로 설정 후 돌아간다.

5. 방문했던 정점들 중 이동 가능 횟수의 최댓값 +1로 이동 가능 횟수를 설정하고 돌아간다.

 

 

 

import sys
sys.setrecursionlimit(10**6)
n, m = map(int, sys.stdin.readline().split())
map = [list(sys.stdin.readline().rstrip()) for _ in range(n)]

dp = [[0] * m for _ in range(n)]
move_list = [[-1,0],[1,0],[0,-1],[0,1]]

def dfs(i, j):
    dp[i][j] = -1
    if map[i][j] == 'H':
        dp[i][j] = 0
        return

    cnt = 0
    check = []
    for ay, ax in move_list:
        mul = int(map[i][j])
        dy,dx = mul*ay+i,mul*ax+j
        if 0>dx or 0>dy or n<=dy or m<=dx:
            cnt += 1
            continue
        if dp[dy][dx] == 0:
            dfs(dy, dx)
        check.append((dy, dx))

    if cnt == 4: # 이동 가능한 정점이 존재하지 않음
        dp[i][j] = 1
        return
    
    for dy, dx in check:
        if dp[dy][dx] == -1: # 사이클이 생기는 정점을 방문
            dp[i][j] = -1
            return
        dp[i][j] = max(dp[i][j], dp[dy][dx]+1) # 이동 횟수가 최대인 정점 +1로 설정
        
dfs(0,0)
print(dp[0][0])

 

 

---

 

각 정점의 이동 횟수를 저장하는 방식과 사이클 생성 원인을 파악하는 것이 핵심인 문제이다.