[파이썬] 백준 1520 : 내리막길 (골드3)

[파이썬] 백준 1520 : 내리막길 (골드3)

1520번: 내리막 길

---

문제

---

풀이

0. 방향성 생각

• DFS사용

1. 입력

import sys
sys.setrecursionlimit(10**6)
input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(h)]
visit = [[-1]*w for _ in range(h)]

 

2. DFS 함수 정의

step = [(1,0),(0,1),(-1,0),(0,-1)]
def dfs(x,y):
    
    if (x,y) == (w-1,h-1):
        return 1
    
    if visit[y][x] != -1:
        return visit[y][x]
    
    answer = 0
    for i in range(4):
        dx,dy = step[i]
        nx = x + dx
        ny = y + dy
    
        if 0<=nx<w and 0<=ny<h and arr[y][x] > arr[ny][nx]:
            answer += dfs(nx,ny)
            
    visit[y][x] = answer
    return visit[y][x]
print(dfs(0,0))

• 목적지 도달하면 개수 1개 세기.
• 도착 했으면 재귀함수 탈출하면서 answer에 추가된다.
• 그 answer 값이 도착점 바로 전인 visit[y][x]에 저장되고 그 값을 리턴한다.
• 또 탈출한 재귀함수에서 answer += dfs(nx,ny)에 위치하고 있을텐데 이 작업이 반복된다.
• 만약 재방문 하는경우에는 이미 다른 경로에서 끝까지 탐색했으므로 visit[y][x]을 리턴해서 재귀함수를 탈출하고 answer에 추가한다.

---

전체코드

import sys
sys.setrecursionlimit(10**6)
input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(h)]
visit = [[-1]*w for _ in range(h)]

step = [(1,0),(0,1),(-1,0),(0,-1)]
def dfs(x,y):
    
    if (x,y) == (w-1,h-1):
        return 1
    
    if visit[y][x] != -1:
        return visit[y][x]
    
    answer = 0
    for i in range(4):
        dx,dy = step[i]
        nx = x + dx
        ny = y + dy
    
        if 0<=nx<w and 0<=ny<h and arr[y][x] > arr[ny][nx]:
            answer += dfs(nx,ny)
            
    visit[y][x] = answer
    return visit[y][x]
print(dfs(0,0))

코멘트

DFS 재귀 싫다.