[BOJ] Q1520 내리막길

[BOJ] Q1520 내리막길

Question

Language: Python

Difficulty: Gold 4

해당 문제는 bfs/dfs을 통한 경로의 개수를 찾는 문제이다.

이 문제를 dfs을 이용해서 가능한 모든 경로에 탐색을 진행하게 되면 최대 경우의 수가 4^500*500으로 수많은 경우의 수가 나온다 –> 시간 초과가 발생하게 된다.

조금 더 효율적으로 접근 하기 위해서는 중간에 중복되는 경로들에 대해서 저장해둘 필요가 있다. –> Memoization 바로 DP를 결합하는 것이다.

만약 어떤 칸에 도달했는데, 이 칸이 이전에 방문했었던 칸이라면 더 이상 dfs을 수행하지 않고 저장되어 있는 값을 이용한다.

dfs + dp 문제는 이러한 경로 개수를 구하는 유형의 문제에서 많이 활용된다.

Solution

import sys

def solution(y,x):
    global visited
    #목적지에 도달하는 경우 경로 1개 추가
    if y==h-1 and x==w-1:
        return 1
    #이전에 방문했던 곳이라면 더 이상 dfs 진행 하지 않는다.
    if visited[y][x] != -1:
        return visited[y][x]
      
    visited[y][x]=0

    for dir in range(4):
        new_y=y+dy[dir]
        new_x=x+dx[dir]
        
        if new_y < 0 or new_y >=h or new_x <0 or new_x>=w:
            continue
  
        if graph[y][x] <= graph[new_y][new_x]:
            continue
          
        #DFS+DP을 활용해서 중복되는 연산을 최소화한다.
        visited[y][x]+=solution(new_y,new_x)    
      
    return visited[y][x]
    
if __name__ == "__main__":
    sys.setrecursionlimit(10**6)
    dy=[-1,0,1,0]
    dx=[0,1,0,-1]
    h,w=map(int,input().split())
    graph=[list(map(int,input().split())) for _ in range(h)]
    visited=[[-1] * w for _ in range(h)]
    print(solution(0,0))