[알고리즘/백준] 1103번 게임 Python 파이썬

 

이번 문제는 어려웠고 사실상 거의 다른 분의 코드를 참고하면서 풀어서 원래 기록하지 않을려고 했지만, 후에 제가 까먹어도 보고 이해할 수 있게 제가 이해한 것을 풀어서 설명하기 위해 적게 되었습니다. 먼저 해당 문제를 더 잘 이해할려면 기본적으로 DFS와 DP에 대해 개념을 알고 있어야합니다.

 

 

각 보드판에 적힌 숫자만큼 위아래좌우로 이동할 수 있고 이렇게 움직였을 때 최대한 많이 움직일 수 있는 숫자를 구하는 것이 관건인 문제입니다. 여기서 예외가 있다면 H 라는 구멍이 존재한다는 것과 갔던 곳을 또 갈 수 있기 때문에 무제한 동전이 움직일 수 있다는 점입니다. 

 

처음에 이 문제를 보고 DFS, BFS 가 생각났고 이중에서 사방면을 검사하는데 많이 쓰이는 DFS 를 써야겠다고 생각했습니다. 다만 문제를 봤을 때 모든 경우를 다 탐색해야하는 문제이기 때문에 어떻게 풀어야 정말 많은 모든 수를 검사하지 않고 넘길 수 있을까 고민했고 그 고민을 다른 분의 DP 를 참고해서 찾을 수 있었습니다.

 

DP란 다이나믹 프로그래밍으로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것입니다. 즉 기존 값을 저장해서 미래 계산에서 다시 검사하지 않고 기존 값을 이용해 계산 비용을 줄여나가는 것이라 이해했습니다.

 

일단, 다음과 같은 코드를 통해 통과하였습니다.

 

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

N, M = map(int, input().split())
map_list = [list(input()) for _ in range(N)]
visited = [[False]*M for _ in range(N)]
dp = [[0]*M for _ in range(N)]

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

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

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

 

위 코드에서 설명할 부분에 대해 이야기하자면, 

먼저 기본적으로 지도 크기, 지도 숫자 값을 받아주고

들렸는지 안 들렸는지 확인하는 visited 지도 <- 무한 루프 확인 필요해서

기존 값을 저장해주는 지도 dp

사방면 검사할 때 쓰이는 dx dy 배열을 생성해줍니다.

 

이제 예제를 들어 설명하고자 합니다 문제에서 왼쪽 상단부터 시작한다고 했으니 0, 0 좌표에서 0 움직임으로 스타트 합니다. dfs에 특정 값이 들어왔을 때 전역변수 result에 기존 result 값과 들어온 값을 비교해서 저장해줍니다. 일단 dfs 가 들어왔다는 자체가 한번 움직였다는 것이고 그 값이 최대값이 되는지 안되는지 확인을 위한 것입니다. 만약에 다른 루트에서 최대값이 이미 들어왔다면 n 값이 저장안될 수도 있습니다. 

 

그리고 해당 지점에서 사분면 방향으로 해당 지도에 쓰인 숫자만큼 움직일 수 있는지 확인해주는데 이때 지도 범위에 안 벗어났는지, 구멍이 아닌지, 움직였을때 기존보다 더 많이 움직여서 해당 위치에 도착했는지(아니라면 해당 경우는 확인해줄 필요가 없어지기 때문에) 확인해줍니다. 

 

그 이후에 이미 들린 곳인지 아닌지 판별해주는데 만약에 들린 곳이면 무한 빙빙 도는 경우라는 것이 성립됩니다. 위 경우도 무사히 넘겼다면 그 위치는 움직일 수 있는 위치로 판별되고 dp 에 업데이트 및 들렸다는 것을 표기 후 재귀함수로 dfs를 호출해줍니다. 그렇게 되면 호출한 위치에서 뻗어나갈 수 있는 곳까지 뻗어나가며 값들을 저장해줄 것이고 후 다른 위치에서 검사할때 해당 값들을 가지고 걸러낼 수 있을 것입니다.

 

여기까지 제가 이해한 바를 바탕으로 작성했습니다. 이렇게 다른 사람 코드 보면서도 따라나가는데 100퍼센트 자세히 이해하기는 어려운 거 같습니다. 과연 제가 나중에 풀이 안보고 짤 수 있을지....ㅠ 그날이 올 수 있을 때까지 열심히 풀어야겠습니다.