문제 설명
•
크기의 동굴 맵이 주어질 때, (0, 0)에서 (N - 1, N - 1)까지 이동하는 최단 경로를 구하는 문제
예제 입력/출력
•
입력1
3
5 5 4
3 9 1
3 2 7
5
3 7 2 0 1
2 8 0 9 1
1 2 1 8 1
9 8 9 2 0
3 6 5 1 5
7
9 0 5 1 1 5 3
4 1 2 1 6 5 3
0 7 6 1 6 8 5
1 1 7 8 3 2 3
9 4 0 7 6 4 1
5 8 3 2 4 8 3
7 4 8 4 8 3 4
0
Plain Text
복사
•
출력1
Problem 1: 20
Problem 2: 19
Problem 3: 36
Plain Text
복사
제약 조건
•
문제 풀이
접근1 브루트포스 (완전 탐색) -
접근2 그리디
접근3 BFS + DP -
•
접근4 다익스트라 -
◦
이 문제는 가중치가 있는 최단 경로 문제이므로 다익스트라를 사용하여 해결할 수 있다.
▪
모든 가중치가 양수(0~9)
◦
다익스트라는 우선순위 큐(힙)를 사용하여 가장 비용이 적은 경로를 먼저 탐색하기 때문에 모든 간선을 동일하게 취급하는 BFS와 달리 빠르게 최소 경로를 탐색할 수 있다.
◦
접근 방법
1.
각 칸을 하나의 노드로 간주하고 (x, y) 좌표를 기반으로 최소 비용을 갱신
2.
우선순위 큐(힙)를 사용하여 현재 최소 비용이 드는 경로부터 처리
3.
(N - 1, N - 1)에 도착할 때까지 최소 비용을 계속 갱신
풀이 코드
접근3 BFS + DP -
•
접근4 다익스트라 -
import heapq
INF = int(1e9)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
t = 0
while True:
t += 1
N = int(input())
if N == 0:
break
adj_matrix = [[0] * (N + 1)] # 동굴 행렬
for _ in range(N):
adj_matrix.append([0] + list(map(int, input().split())))
# 다익스트라 알고리즘
dist_matrix = [[INF] * (N + 1) for _ in range(N + 1)] # 최단 거리 행렬
dist_matrix[1][1] = adj_matrix[1][1] # 시작 노드 초기화
hq = [] # 힙 자료구조
heapq.heappush(hq, (adj_matrix[1][1], 1, 1)) # (비용, x, y)
while hq:
cur_dist, x, y = heapq.heappop(hq)
for d in range(4):
nx = dx[d] + x
ny = dy[d] + y
if (0 < nx <= N) and (0 < ny <= N):
tmp_dist = cur_dist + adj_matrix[ny][nx]
if tmp_dist < dist_matrix[ny][nx]:
dist_matrix[ny][nx] = tmp_dist
heapq.heappush(hq, (tmp_dist, nx, ny))
print(f"Problem {t}: {dist_matrix[N][N]}")
Python
복사
