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

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

728x90

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

import sys, heapq # 동서남북 dx = [0, 0, -1, 1] dy = [1, -1, 0, 0] count = 1 # 순서 def dijkstra(): queue = [] heapq.heappush(queue, (graph[0][0], 0, 0)) # 시작 노드 큐에 삽입 dist[0][0] = graph[0][0] while queue: cur_dist, x, y = heapq.heappop(queue) # 현재 노드 비용, x값, y값 if cur_dist > dist[x][y]: # 현재 노드 비용이 더 크다면 넘어감 continue for i in range(4): # 동서남북 노드 확인 xi = x + dx[i] yi = y + dy[i] if 0 <= xi < n and 0 <= yi < n: # 범위 내에 있다면 cost = cur_dist + graph[xi][yi] # 비용 계산 if cost < dist[xi][yi]: # 비용이 dist값보다 작으면 heapq.heappush(queue, (cost, xi, yi)) # 해당 노드 큐에 삽입 dist[xi][yi] = cost # 비용 수정 while True: n = int(input()) if n == 0: break graph = [list(map(int, input().split())) for _ in range(n)] dist = [[sys.maxsize] * n for _ in range(n)] dijkstra() print(f'Problem {count}: {dist[n-1][n-1]}') count += 1

1. 필요한 정보를 입력받고 필요한 변수를 생성한다.

2. 다익스트라를 수행한다.

2-1. 우선순위 큐를 생성하고 시작노드의 비용은 graph[0][0]으로 만든다. 큐에 시작 노드를 삽입하는데 꼭 (비용, x위치, y위치) 순으로 넣어야 한다.

2-2. 큐에 값이 없을 때까지 다음을 반복한다.

2-3. 큐에서 현재 노드를 가져온다. 현재 노드의 비용이 dist 값보다 크면 비교할 것도 없으므로 넘어간다.

2-4. 그렇지 않다면 현재 노드와 동서남북으로 연결된 노드를 가져온다. 연결된 노드의 비용를 계산하고 그 비용이 dist의 값보다 작다면 큐에 삽입한 후 비용을 수정한다.

3. 결과를 출력한다.

728x90

from http://soohyun6879.tistory.com/236 by ccl(A) rewrite - 2021-11-24 12:26:42