[백준 BOJ_1103] 게임 Python 풀이

출처: 백준 온라인 저지

문제

풀이

동적계획법을 더한 DFS으로 풀었습니다.

cache는 다음과 같습니다.

cache[y][x] = 좌표 (x, y)까지 도달하는 최장거리 

visited를 따로 만들어주어 cycle 체크를 해주었습니다. 이미 방문했다면 cycle이 있으므로 -1을 출력해주고 바로 exit()해주어 재귀함수를 더 이상 진행하지 않도록 했습니다.

cache를 확인해주며 cache의 값보다 클 경우에만 dfs를 돌아주었습니다.

코드

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

N, M = map(int, input().split())

graph = [ list(input().rstrip()) for _ in range(N)]
visited = [[ 0 for _ in range(M)] for _ in range(N)]
cache = [[ 0 for _ in range(M)] for _ in range(N)]

result = 0

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

def dfs(y, x, cnt):
  global result

  result = max(result, cnt)
  num = int(graph[y][x])

  for i in range(4):
    ny, nx = y+num*dy[i], x+num*dx[i]
    if 0 <= ny < N and 0 <= nx < M and graph[ny][nx] != "H" and cnt+1 > cache[ny][nx]:
      if visited[ny][nx]:
        print(-1)
        exit()
      
      cache[ny][nx] = cnt + 1
      visited[ny][nx] = 1
      dfs(ny, nx, cnt+1)
      visited[ny][nx] = 0

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