백준 1520 <내리막 길> Python

https://www.acmicpc.net/problem/1520

---

단순한 BFS, DFS 로 진행하면 시간초과가 발생합니다.

그래서 한번에 모든 길을 찾는게 아닌 중간중간 가능한 경로를 합해주며 진행하겠습니다.

 

A - B - C - D - E - F

A - B - G - D - E - F

 

두 경로로 이동이 가능하다고 가정하면

D 의 지점에서 D 까지 도달하는 경로를 병합한 뒤, D 에서 F 까지는 한 번만 탐색하는 방식입니다.

 

해당 방식을 구현하기 위해 DFS 와 heapq 를 사용했습니다.

D 에서 탐색을 시작하기 전에 D 보다 높은 지점에서의 이동 먼저 계산하기 위함입니다.

그러므로 heapq 안의 구성요소는 [높이, [인덱스]] 가 됩니다.

 

일반적으로 heapq 는 최소힙을 기본으로 하기 때문에 최대힙을 사용하기 위해 입력과 출력시 -1 을 곱해주어야합니다.

예시를 풀이하는 과정입니다.

빨간 사각형은 현재 노드, 파란 사각형은 heapq 에 들어있는 노드 입니다.

노드 안의 수는 높이, 해당 노드를 거쳐가는 경로의 수 입니다.

---

import sys

import heapq

input = sys.stdin.readline

def solution(M, N, data_map):

    # 이동 가이드

    move_guide = [[0, 1], [0, -1], [1, 0], [-1, 0]]

    # 방문 횟수 리스트

    visited = [[0 for _ in range(N)] for __ in range(M)]

    visited[0][0] = 1

    # 큐

    hq = [[-data_map[0][0], [0, 0]]]

    # 순회

    while hq:

        # 현재 높이, 현재 인덱스

        now_height, [now_x, now_y] = heapq.heappop(hq)

        now_height *= -1

        # 이동 가능한 위치 순회

        for x, y in move_guide:

            # 다음 인덱스

            next_x, next_y = now_x + x, now_y + y

            # 이동 가능한 위치면

            if (next_x >= 0 and next_x < M) and (next_y >= 0 and next_y < N):

                # 다음 위치의 높이가 더 낮으면

                if data_map[next_x][next_y] < now_height:

                    # 방문한 적이 없다면

                    if not visited[next_x][next_y]:

                        # 큐에 삽입

                        heapq.heappush(hq, [-data_map[next_x][next_y], [next_x, next_y]])

                    # 방문 횟수 최신화

                    visited[next_x][next_y] += visited[now_x][now_y]

    return visited[M-1][N-1]

# 입력

M, N = map(int, input().strip().split())

data_map = [list(map(int, input().strip().split())) for _ in range(M)]

print(solution(M, N, data_map))