문제: https://www.acmicpc.net/problem/1890
처음에는 BFS로 풀어보려다가 메모리 초과가 나서 찾아보니까 방문 표시가 필수라고..! 최악의 경우 BFS의 너비만큼 O(2^n)까지 갈 수 있다.
그렇다고 방문표시하면 답이 틀려가지고(한번 방문했더라도 상관없이 방법의 수를 추가하기 때문) 고민했다 DP로 풀 수 있는 방법을..
이게 초기방식이다.
#실패한 풀이
def get_paths_bfs(n, board):
dp = [[0] * n for _ in range(n)]
queue = deque([(0, 0)]) #시작점 (0, 0)
while queue:
cur_x, cur_y = queue.popleft()
move = board[cur_x][cur_y]
if cur_y + move < n and move > 0:
dp[cur_x][cur_y+move] += 1
queue.append((cur_x, cur_y + move))
if cur_x + move < n and move > 0:
dp[cur_x+move][cur_y] += 1
queue.append((cur_x + move, cur_y))
return dp[n-1][n-1]
결국 다른 풀이를 참고해서 DP로 풀 수 있는 방법을 알아냈다. 여전히 내겐 어려운 DP..🤦🏻♀️
차례대로 그래프를 순회하면서 dp[x+jump값][y] += dp[x][y]
, dp[x][y+jump값] += dp[x][y]
와 같이 dp값을 갱신하는 방식이다.
def get_paths_dp(n, board):
dp = [[0] * n for _ in range(n)]
dp[0][0] = 1
for i in range(n):
for j in range(n):
jump = board[i][j]
if jump == 0: break
if jump + i < n:
dp[jump+i][j] += dp[i][j]
if jump + j < n:
dp[i][jump+j] += dp[i][j]
return dp[n-1][n-1]