1890번 점프

개발새발log·2022년 5월 2일
0

백준

목록 보기
3/36

문제: 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]
profile
⚠️ 주인장의 머릿속을 닮아 두서 없음 주의 ⚠️

0개의 댓글