백준 1103 게임

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/1103

풀이

난이도 : Gold II

이 문제는 dfs로 모든방향을 탐색하면서 dp를 함께 사용하는 것이 가장 중요한 점이다.
visited는 재귀적인 dfs 전에 True로 만들고, 끝난 후에 다시 False로 만들지만 dp값은 계속 저장을 해나가면서 진행한다.
따라서 이미 탐색을 진행했던 곳일 때 dp를 참조하여 다시 방문할 필요가 없다고 판단을 할 수 있다.

1. dfs로 네 방향을 해당 그래프의 숫자만큼 이동하도록 탐색하면서 dfs의 depth(코드에서는 count)를 같이 인자로 넘겨준다.
2. dfs안에서 dfs를 재귀적으로 실행하기전에 dp 값을 채워주고, visited도 기록해준다.
   (재귀적인 dfs가 끝나면 해당 그래프의 visited는 다시 False값으로 만들어준다.)
3. visited가 True인 곳을 방문한다면 무한루프로 계속 방문할 수 있다는 이야기이므로 -1을 출력하고 종료한다.
4. 전역변수로 지정해둔 result값을 dfs를 실행할 때마다 인자로 넘겨주는 depth값 중 최대값으로 기록을 해주면서
   더 이상 탐색을 진행할 수 없으면 코드가 종료되면서 result+1 을 print해준다.

코드

    from collections import deque
    import sys

    sys.setrecursionlimit(10**6)

    n, m = map(int, input().split())
    graph = []
    visited = [[False] * m for _ in range(n)]
    dp = [[0] * m for _ in range(n)]

    for _ in range(n):
        graph.append(list(input().rstrip()))

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

    result = 0

    def dfs(x, y, count):
        global result
        result = max(result, count)

        for i in range(4):
            nx = x + dx[i]*int(graph[x][y])
            ny = y + dy[i]*int(graph[x][y])

            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue
            if graph[nx][ny] == "H" or count+1 <= dp[nx][ny]:
                continue

            if visited[nx][ny]:
                print(-1)
                exit()

            dp[nx][ny] = count + 1
            visited[nx][ny] = True
            dfs(nx, ny, count+1)
            visited[nx][ny] = False

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