[백준 1103] 게임 (python)

1103번: 게임

---

 

처음에 DFS만 사용했더니 시간초과가 났다. 다른 사람 코드를 보니 DP를 사용하더라..

최대값을 구해야 하는 것이니 dp에 값을 저장해 이전값보다 작은 값이면 진행하지 않도록 하자

 

1. 방문 여부를 저장하는 visited 배열을 생성한다.
2. 움직인 횟수를 저장하는 dp 배열을 생성한다.
3. 시작점에서 네방향으로 움직이되 바깥으로 나가지 않고, 구멍이 아니고, 이전보다 움직인 횟수(cnt+1)가 많다면 진행한다.
4. 만약 방문했던 곳이라면 무한 루프에 돌 수 있으므로 -1 출력하고 종료한다.
5. 아니라면 dp와 visited를 update해주고 진행한다.
6. 마지막 좌표에서 바깥으로 빠지거나 구멍에 빠져도 되니 한번 더 움직일 수 있으므로 result + 1을 출력한다.

 

import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

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

visited = [[False]*M for _ in range(N)]
dp = [[0]*M for _ in range(N)]

result = 0
def dfs(x, y, cnt):
    global result
    result = max(result, cnt)
    for i in range(4):
        nx = x+int(arr[x][y])*dx[i]
        ny = y+int(arr[x][y])*dy[i]
        if 0 <= nx < N and 0 <= ny < M and arr[nx][ny] != "H" and cnt+1 > dp[nx][ny]:
            if visited[nx][ny]:
                print(-1)
                exit()
            else:
                dp[nx][ny] = cnt+1
                visited[nx][ny] = True
                dfs(nx, ny, cnt+1)
                visited[nx][ny] = False

dfs(0, 0, 0)
print(result+1)