[python] 백준 1103 게임

 

문제 해결

• DFS를 써야한다는 것은 쉽게 파악할 수 있다.
• 다만 떨어질 때 까지 옮겨지는 횟수를 세는 것으로 숫자가 커질 수 있으므로 dp를 사용하여한다.
  • 숫자가 커지면 거의 DP를 사용해야 하는 것 같다.
• 한번 방문한 곳을 또 방문할 수 있으면 사이클을 돌 수 있고 무한반복이 가능하므로 -1을 출력하면 된다.
• 그렇지 않으면 떨어질 때 까지 혹은 방문한 지점이 나타날 때 까지 계속해서 DFS를 이용해서 나아가면 된다.

 

CODE

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

def dfs(sx, sy, cnt):
    global answer
    answer = max(answer, cnt)
    dxs = [1,-1,0,0]
    dys = [0,0,1,-1]

    for dx, dy in zip(dxs,dys):
        nx = sx+ dx*int(board[sx][sy])
        ny = sy+ dy*int(board[sx][sy])

        if 0<=nx<n and 0<=ny<m and board[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] = 1
                dfs(nx, ny, cnt+1)
                visited[nx][ny] = 0
if __name__=='__main__':
    n, m = map(int, input().split())
    board = [list(str(input().rstrip())) for _ in range(n)]
    visited = [[0 for _ in range(m)] for _ in range(n)]
    dp = [[0 for _ in range(m)] for _ in range(n)]
    answer = 0
    dfs(0,0,0)
    print(answer + 1)