[백준/Python] 4485번 녹색 옷 입은 애가 젤다지?

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

4485번: 녹색 옷 입은 애가 젤다지?

문제분석

1. 분류
   • 그래프 이론, 다익스트라
2. 문제설명
   • 입력은 여러 개의 테스트 케이스로 이루어져 있다.
   • 각 테스트 케이스의 첫째 줄에는 동굴의 크기를 나타내는 정수 N(2 ≤ N ≤ 125)이 주어진다. → 동굴의 크기는 NxN
   • N=0인 입력이 주어지면 전체 입력이 종료된다.
   • [0][0]에서 [N-1][N-1]까지 가는 동안 지나는 칸의 크기만큼 소지금을 잃는다.
   • 잃는 금액을 최소로 하여 이동해야 하며, 한 번에 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다.
   • 잃을 수 밖에 없는 최소 금액을 출력한다.

 

코드

1	import sys, heapq
2
3	def dijkstra(cave, cost, x, y):
4	n = len(cave)
5	pq = []
6
7	heapq.heappush(pq, (cave[x][y], x,y))      # 동굴의 각 칸의 크기를 우선순위 큐에 넣는다.
8	while pq:
9	curr_cost, curr_x, curr_y = heapq.heappop(pq)
10	if cost[curr_x][curr_y] < curr_cost:      # 이미 최소 비용을 구한 경우 다음으로 넘어간다.
11	continue
12
13	for i in range(4):
14	next_x, next_y = curr_x + dx[i], curr_y + dy[i]
15	if 0 <= next_x < n and 0 <= next_y < n:
16	next_cost = cave[next_x][next_y]
17	if curr_cost + next_cost < cost[next_x][next_y]:
18	heapq.heappush(pq, (curr_cost + next_cost, next_x, next_y))
19	cost[next_x][next_y] = curr_cost + next_cost
20
21	return cost[n-1][n-1]
22
23	input = sys.stdin.readline
24	dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
25	inf = int(1e5)
26	tc = 1
27	while True:
28	n = int(input())
29	if n == 0: break     # 0을 입력받으면 종료
30
31	cave = [list(map(int, input().split())) for _ in range(n)]
32	cost = [[inf] * n for _ in range(n)]    # 시작점[0][0]부터 도착지점[N-1][N-1]까지 잃게 되는 루피의 크기
33
34	answer = dijkstra(cave, cost, 0, 0)
35	print('Problem {}: {}'.format(tc, answer))
36	tc += 1

 

문제풀이

• [0][0]에서 [N-1][N-1]까지 도둑루피의 크기가 최소가 되는 경로를 다익스트라로 구한 후 잃게 되는 루피 값을 출력한다.
• 우선순위 큐를 활용하여 다익스트라, BFS 알고리즘을 수행한다.