백준 1103 게임 python

DFS로 움직이면서 visit배열로 방문여부를 체크해줬다.
방문 했는데 또 방문했다면 순환이 이뤄지는 것이므로 무한번 움직일 수 있다.

그런데 이방법은 시간초과가 발생했다.
추가적인 조치가 필요해 보였다.

📜 문제 바로 가기 : 게임

제출코드

파이썬

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
board = [input().rstrip() for _ in range(N)]

ans = 0
visit = [[False] * M for _ in range(N)]
delta = [(0, 1), (0, -1), (1, 0), (-1, 0)]

memoization = [[[0 for _ in range(4)] for _ in range(M) ] for _ in range(N)]

def isRange(i, j):
    if 0 <= i < N and 0 <= j < M:
        return True
    return False

def DFS(i, j, cnt):
    global ans
    if ans == -1 :
        return
    
    ans = max(cnt, ans)
    
    m = int(board[i][j])
    for n in range(4):
        if memoization[i][j][n] == 0:
            di, dj = delta[n]
            ni, nj = i + di*m, j + dj*m
            if isRange(ni, nj) and board[ni][nj] != "H":
                if visit[ni][nj] == True:
                    ans = -1
                    return
                visit[ni][nj] = True
                DFS(ni, nj, cnt+1)
                memoization[i][j][n] = max(memoization[ni][nj]) + 1
                visit[ni][nj] = False
            else:
                if ans != -1:
                    ans = max(ans, cnt+1)

                memoization[i][j][n] = 1

DFS(0, 0, 0)
if ans == -1:
    print(-1)
else:
    print(max(memoization[0][0]))

---

접근방법

시간초과를 해결하기 위한 방법

DP를 적용했다.
각 좌표에 4방향으로 움직일 수 있는 배열( memoization )을 만들고 그 위치에 그 방향으로 이동시 최대로 움직일 수 있는 횟수를 저장해줬다.

만약 어떤 좌표 (i, j)에 도착하고 n방향의 memoization 배열값이 존재한다면
( memoization[i][j][n] != 0 )

그 방향으론 이전에 한번 거쳐서 확인을 해봤다는 의미이므로 확인하지 않는 방법으로 시간을 줄일 수 있었다.