[BOJ] Q1890 점프

[BOJ] Q1890 점프

Question

Language: Python

Difficulty: Silver 1

각 칸에서는 칸에 적힌 값 만큼 오른쪽, 혹은 아래쪽으로 이동할 수 있다. –> 경로 찾기 문제 + 경로의 개수를 구해야 하니 중간 중간에 해당 칸으로 도달할 수 있는 경로의 개수를 저장하는 Memoization이 필요하다 이러한 유형은 DFS/BFS DP 문제의 일종으로 DFS/BFS 과정에서 DP를 활용하는 문제이다.

Fail

from collections import deque
def solution(row,col):
    if row==num-1 and col==num-1:
        return 1
    if dp[row][col] == -1:
        dp[row][col]=0
    
    value=graph[row][col]
    for new_row,new_col in [(row+value,col),(row,col+value)]:
        if new_row < 0 or new_row >= num or new_col <0 or new_col >=num:
            continue
        dp[row][col]+=solution(new_row,new_col)
    
    return dp[row][col]
    
if __name__ == "__main__":
    num=int(input())
    graph=[list(map(int,input().split())) for _ in range(num)]
    dp=[[-1] * num for _ in range(num)]
    print(solution(0,0))

하지만 이 문제를 이렇게 DFS DP 방식으로 풀어보니 시간 초과가 났다. 조금만 더 쉽게 생각해보니, 그냥 모든 칸을 다 돌면서 그 칸에 도달할 수 있으면 이전 칸의 경로 값을 더해주기만 하면 된다. 대신, 이 문제는 방향이 오른쪽, 아래 방향으로 이동 가능하기 때문에 다음과 같은 풀이로 가능하다. 만약 방향이 4가지가 있다면 이는 DFS DP 방식으로 풀어야한다.

Solution

def solution():
    checked=[[0] * (num) for _ in range(num)]
    checked[0][0]=1

    for i in range(num):
        for j in range(num): 
            if i==num-1 and j==num-1:
                return checked[num-1][num-1]
            value=graph[i][j]
          
            for new_i,new_j in [(i+value,j),(i,j+value)]:
                if new_i >=num or new_j >=num:
                    continue
                
                checked[new_i][new_j]+=checked[i][j]
            

    
if __name__ == "__main__":
    num=int(input())
    graph=[list(map(int,input().split())) for _ in range(num)]
    print(solution())