[백준] 1520번: 내리막 길 파이썬 풀이 (bottom-up, 비재귀)

사용한 기술 스택들:  

 

1520번: 내리막 길 (acmicpc.net)

1520번: 내리막 길

 

이 문제를 풀다가 DFS+DP로 재귀적으로 푸는 방법들만 인터넷에 올라왔길래 백준 질문게시판에서 본 우선순위 큐와 BFS를 접목한 비 재귀 풀이 방법을 소개해 보려고 한다.

 

처음에 이 문제를 접했을 때 재귀는 좋아하지 않아서 비 재귀(bottom-up) 방법을 찾다가 이런 글을 봤다.

 

글 읽기 - dfs + dp 말고 bfs + pq로 풀었습니다만, (acmicpc.net)

글 읽기 - dfs + dp 말고 bfs + pq 로 풀었습니다만,

 

이 풀이를 보고 파이썬으로 좀 더 간단하게 풀은 것을 공유해보자 한다.

 

코드 구조:

import sys
import heapq

def BFS():
    queue = [(-table[0][0],0,0)]
    direction = [(1,0),(-1,0),(0,1),(0,-1)]
    visited = [[0]*m for _ in range(n)]
    visited[0][0] = 1
    while queue:
        h,x,y = heapq.heappop(queue)
        for dx,dy in direction:
            nx=dx+x
            ny=dy+y
            if 0<=nx<n and 0<=ny<m and table[nx][ny]<table[x][y]:
                if visited[nx][ny] ==0:
                    heapq.heappush(queue,(-table[nx][ny],nx,ny))
                visited[nx][ny] += visited[x][y]
    return visited[n-1][m-1]
input = sys.stdin.readline
n,m = map(int,input().split())
table = [list(map(int,input().split()))for _ in range(n)]
print(BFS())

위에 코드를 보면 그냥 BFS와 구조가 아주 비슷한 것을 볼 수 있다. 다른 점은 heapq를 deque 대신에 사용했다는 것과 밑에 있는 코드가 추가되었다는 것이다. heapq와 PriorityQueue 차이는 이 블로그를 참고하자.

if visited[nx][ny] ==0:
	heapq.heappush(queue,(-table[nx][ny],nx,ny))
visited[nx][ny] += visited[x][y]

로직은 이렇다. 왼쪽 끝에 있는 계단을 (-높이, x 좌표, y 좌표) 순으로 넣어주고 시작한다. queue에 넣을 때마다 높이를 -로 바꾸어 주는 이유는 heapq는 기본이 min-heap이라 최솟값이 pop이 되기 때문에 -높이를 튜플의 첫 번째 인자로 설정해주면 max-heap으로 바꾸어져서 큰 값부터 순서대로 나올 수 있다.

 

(0,0) 좌표의 visited 값을 1로 설정하고 visited [a][b]를 (a, b)까지 갈 수 있는 방법이라 생각하자. 상하좌우에서 있는 좌표에서 a, b로 오면 visited [a][b]에 있는 경로의 개수 수와 왔던 좌표의 경로의 수를 더해준다. 이해가 되지 않는다면 밑에 있는 그림을 보자.

 

 

처음에 0으로 초기화시키고 1을 0,0에 설정해준다.

 

 

도착하는 노드마다 자신의 경로 수를 더해준다.

 

이렇게 더해 나가다 보면 오른쪽 밑에 왼쪽 위에서 오른쪽 밑까지 갈 수 있는 경로의 수가 저장된다.

 

저기에 있는 화살표를 큰 숫자에서 작은 숫자로 갈 수 있는 경로로 생각하면 이 문제도 똑같이 풀 수 있다.

visited[nx][ny] += visited[x][y]

딱 이 부분의 코드가 위에서 설명하는 부분이다.

 

그러면 이쯤에서 이렇게 생각할 수도 있다. 그냥 heapq를 쓰지 않고 queue로 bfs를 쓰면 되는 거 아닌가? 여기서 문제가 발생한다. 밑의 예제를 보자.

4 5
50 45 37 32 30
35 50 40 20 25
30 30 25 17 28
27 24 22 15 10

 

여기서 32,30,20,25가 있는 부분에서(오른쪽 위) 문제가 발생한다. 32에서 20으로 가거나 32에서 30으로 가는 걸 bfs로 풀면 20에는 32에서 온 것밖에 도착하지 않아서 20은 1이 되고 17에 2가 아닌 1이 전파되는 게 발생한다. 설명을 도와주기 위해서 밑의 그림을 보자.

 

빨간색은 전파 순서

BFS만 쓰면 25에서 20으로 갈 때에 이미 20은 17에 전파를 마친 상황이라 17에 2가 업데이트가 되어있지 않는다. 이는 BFS는 간선의 경로를 같은 거리라고 생각하고 전파하기 때문에 더 가까울수록 먼저 update 되는 상황이 발생한다. 여기서 heapq를 queue대신 사용하고 노드의 숫자(예: 30, 25,17)를 첫 번째 인자로 넣어주면(-로 바꿔서 max heap으로 했다는 가정 하에) 20은 20보다 큰 숫자들을 방문하기 전까지는 update가 되지 않기 때문에 17에 2라는 경로가 저장된다. 그리고 맨 왼쪽 밑에 저장되어있는 경로의 수를 출력해주면 AC를 받을 수 있다.

 

비교적 DFS와 재귀 풀이와 비슷한 속도를 보여준다.

 

이렇게 재귀 적보다 비 재귀로 풀면 더 이해하기가 쉽고 어떻게 작동하는지 알기 쉽다. 다음에도 좀 더 신박한 풀이를 들고 오겠다.

코드 링크:

baekjoonProblems/내리막_길.py at c5334692e3bdc2b4714e54d57c7ffbbb66580ede · LimePencil/baekjoonProblems (github.com)

GitHub - LimePencil/baekjoonProblems: 백준 코딩문제 자바&파이썬 해답