백준 1103번 : 게임 in Python
이 문제는 1부터 9까지의 숫자와 구멍이 있는 직사각형 보드에서 게임을 할 때 최대 몇 번의 동전을 움직일 수 있는지를 구하는 문제이다. 동전을 움직이는 규칙은 위와 같다.
이 문제를 해결하기 위해서는 왼쪽 위에서 시작하는 DFS를 수행해 동전의 이동 횟수의 최댓값을 구해야한다. DFS는 재귀 함수로 구현할 수 있다. 우선 함수 구현 전에 각 지점을 방문했음을 나타내는 N*M 크기의 visitied 행렬(초기값은 False)과 동서남북 방향을 나타내기 위한 dx, dy가 필요하다.
이제 DFS 함수를 구현해보자. 우선 DFS 함수는 인자로 방문하고자 하는 지점의 좌표 (x, y)를 받는다. 이 지점을 방문했다는 의미로 visited에서 해당하는 지점의 값을 True로 바꾼다. 그리고 board[x][y]의 값을 변수 d에 저장해 후에 사방으로 얼마나 이동할지를 파악한다. 이제 동서남북 방향으로 d만큼 떨어진 지점의 좌표 (next_x, next_y)를 구한 뒤 해당 지점이 보드 밖 혹은 구멍이 아닌 경우, 그 지점에 대한 DFS 함수를 재귀적으로 호출한다. 단, 해당 지점을 이미 방문한 경우 DFS 특성상 (x, y) 지점의 조상 노드를 방문한 것이기 때문에 사이클이 발생한다. 따라서 이러한 경우 동전을 사이클을 따라 무한히 움직일 수 있으므로 -1을 출력한다. 그렇지 않은 경우에는 정상적으로 (next_x, next_y)에 대해 DFS 함수를 재귀적으로 호출하면 된다. 마지막으로 (x, y) 지점에 대한 visited 값을 False로 바꿔 다른 DFS 경로와 충돌이 일어나는 것을 막는다.
여기에 동전의 이동 횟수의 최댓값을 구하고 싶은 경우에는 사이클이 생기지 않으면서 재귀적으로 함수를 호출한 횟수를 세면 된다. 그러나 이렇게 구현하는 경우 시간 초과 문제가 발생한다. 왜냐하면 경로의 개수가 N, M이 커짐에 따라 기하급수적으로 늘어날 수 있기 때문이다. 그러므로, 최대한 경우의 수를 줄이는 것이 중요한 문제가 된다. 따라서 여기서는 DFS에 더해 dynamic programming을 이용한다.
이를 위해 DFS 함수를 구현하기 전에 각 지점을 방문하기 위한 동전의 이동 횟수의 최댓값을 저장하는 N*M 행렬 dp를 만든다.
그리고 DFS 구현 중 (next_x, next_y)가 보드 밖 혹은 구멍이 아닌 경우를 조사함과 동시에 (next_x, next_y)에 대한 dp 값이 (x, y)에 대한 dp 값에 1을 더한 값보다 작은지를 조사한다. 결국 우리가 구하고 싶은 것은 동전의 이동 횟수의 최댓값이지, 모든 경로를 다 보고 싶은 것은 아니기 때문에, 현재 경로를 통해 얻을 수 있는 동전의 이동 횟수가 다른 경로보다 적으면 굳이 따질 필요가 없기 때문이다.
만약 이 조건을 만족하고, (next_x, next_y)를 방문하지 않았으면 dp[next_x][next_y]를 dp[x][y] + 1로 바꾼다. 그 다음 (next_x, next_y)에 대해 DFS를 재귀적으로 호출한 결과를 조사해 -1인 경우, 즉 사이클이 발생한 경우 -1을 반환하고, 그렇지 않으면 (x, y)에 대한 4방향에 대한 조사로부터 나온 값들 중 가장 큰 값에 1을 더한 값을 반환한다.
이를 코드로 구현하면 다음과 같다.
from collections import deque
N, M = map(int, input().split())
board = []
for _ in range(N):
arr = input()
input_arr = []
for c in arr:
input_arr.append(c)
board.append(input_arr)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# DFS 탐색 중 각 지점을 방문했었는지를 나타내는 행렬
visited = [[False]*M for _ in range(N)]
# 각 지점까지 가기 위한 동전의 이동 횟수의 최댓값을 저장하는 행렬
dp = [[0]*M for _ in range(N)]
# DFS 탐색
def DFS(x, y):
# 인자로 주어진 지점을 방문
visited[x][y] = True
# 이동 거리를 조사
d = int(board[x][y])
# 현재 지점으로부터 가능한 동전의 이동 횟수의 최댓값을 저장하는 변수
res = 0
for i in range(4):
next_x = x + d*dx[i]
next_y = y + d*dy[i]
# 사방으로 d만큼 떨어진 지점이 보드 안이고 구멍이 아닌지,
# 그리고 동전의 이동 횟수의 최댓값을 갱신할 수 있는지를 조사한다.
if 0<=next_x<N and 0<=next_y<M and board[next_x][next_y] != 'H' and dp[next_x][next_y] < dp[x][y] + 1:
# DFS 경로에서 이미 방문한 지점인 경우 사이클이 발생해 무한히 동전을 이동시킬 수 있다.
if visited[next_x][next_y]:
return -1
# 동전의 이동 횟수 최댓값 갱신
dp[next_x][next_y] = dp[x][y] + 1
# d만큼 이동한 지점에 대해 DFS 함수를 재귀적으로 호출하고 그 반환값을 조사한다.
temp = DFS(next_x, next_y)
# 사이클 발생
if temp == -1:
return -1
# 4방향에 대해 구한 temp 값들 중 최댓값을 구한다.
else:
res = max(res, temp)
# 인자로 주어진 지점에 대한 visited 값을 False로 바꿔 다른 DFS 경로와 충돌하지 않도록 한다.
visited[x][y] = False
# 최후에 동전이 보드 밖이나 구멍으로 떨어지는 경우도 포함하기 위해 여기에 1을 더했다.
return res + 1
print(DFS(0, 0))