[python] 다익스트라 알고리즘_전보

9-1.py 다익스트라 알고리즘 소스코드

import sys
imput = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split())
start = int(input())
graph = [[] for i in range(n+1)]
graph = [false] * (n+1)
distance = [INF] * (n+1)

for _ in range(m):
	a, b, c = map(int, input().split())
    graph[a].append((b, c))
    
def get_smallest_node():
	min_value = INF
    index = 0
    for i in range(1, n+1):
    	if distance[i] < min_value and not visited[i]:
        	min_value = distance[i]
            index = i
    return index
    
def dijkstra(start):
	distance[start] = 0
    visited[start] = True
    for j in graph[start]:
    	distance[j[0]] = j[1]
    for i in range(n -1):
    	now = get_smallest_node()
        visited[now] = True
        for j in graph[now]:
        	cost = distance[now] + j[1]
            if cost < distance[j[0]]:
            	distance[j[0]] = cost
 
 dijkstra(start)
 
 for i in range(1, n+1)
 	if distance[i] == INF:
    	print("INFINITY")
    else:
    	print(distance[i])

Q1. 전보

어떤 나라에는 N개의 도시가 있다. 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당메시지를 전송할 수 있다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 한다면, 도시 X에서 Y로 향하는 통로가 설치되어있어야한다. 예를 들어 X에서 Y로 향하는 통로는 있지만 Y에서 X로 향하는 통로가 없다면 Y는 X로 메시지를 보낼 수 없다. 또한 통로를 거쳐 메시지를 보낼 때는 일정한 시간이 소요된다.

어느날 C라는 도시에서 위급상황이 발생했다. 최대한 많은 도시로 메시지를 보내고자 한다. 메시지는 도시 C에서 출발하여 각 도시 사이에 설치된 통로를 거쳐 최대한 많이 퍼져나가야한다. 각 도시의 번호와 통로가 설치되어있는 정보가 주어졌을때 도시 C에서 보낸 메시지를 받게되는 도시의 개수는 총 몇개이며, 도시들이 모두 메시지를 받는데까지 걸리는 시간은 얼마인지 계산하는 프로그램을 작성하시오.

*입력조건

• 첫째줄에 도시의 갯수N, 통로의 갯수 M, 메시지를 보내고자 하는 도시C가 주어진다.

(1<=N<=30,000, 1<=M<=200,000, 1<=C<=N)

-둘째줄부터 M+1번째 줄에 걸쳐서 통로에 대한 정보 X,Y,X가 주어진다. 이는 특정 도시 X에 다른 특정 도시 Y로 이어지는 통로가 있으며 메시지가 전달되는 시간이 Z라는 의미이다.

(1=X,Y<=N, 1<=Z<=10,000)

*출력조건

• 첫째줄에 도시 C에서 보낸 메시지를 받는 도시의 총 개수와 총 걸리는 시간을 공백으로 구분하여 출력한다.

입력 예시

6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2

출력 예시

0
2
3
1
2
4

[문제 아이디어]

한 도시에서 다른 도시까지의 최단거리 문제를 묻는 문제이다.
이때 N,M의 범위가 크기 때문에
힙을 사용한 다익스트라알고리즘으로 해결해야한다.

import heapq
inport sys

input = sys.stdin.readline
INF = int(1e9)

n, m, start = map(int, input().split())
graph = [[] for i in range(n + 1)
distance = [INF] * (n+1)

for _ in range(m):
	x, y, z = map(int, input().split())
   graph[x].append((y, z))

def dijkstra(start):
	q = []
   heapq.heappush(q, (0, start))
   distance[start] = 0
   while q:
   	dist, now = heapq.heappop(q)
       if distance[now] < dist:
       	continue
       for i in graph[now]:
       	cost = dist + i[1]
           if cost < distance[i[0]]:
           	distance[i[0]] = cost
               heapq.heappush(q, (cost, i[0]))

dijkstra(start)

count = 0
max_distance = 0
for d in distance:
	if d != INF:
   	count += 1
       max_distance = max(max_distance, d)

print(count - 1, max_distance)

(해설)

import heapq
import sys

input = sys.stdin.readline # 빠른 입력
INF = int(1e9) # 무한을 의미하는 값으로 10억 설정

# 노드의 개수, 간선의 개수, 시작노드를 입력받기
n, m, start = map(int, input().split())

# 최단거리 테이블
distance = [INF]*(n+1)

# 노드 연결정보
graph = [[] for i in range(n+1)]

for _ in range(m):
  # x번 노드에서 y번 노드로 가는 비용 z
  x,y,z = map(int, input().split())
  graph[x].append((y,z))

# 다익스트라 알고리즘(최소힙 이용))
def dijkstra(start):
  q=[]
  # 시작 노드
  heapq.heappush(q, (0,start))
  distance[start] = 0

  while q:
    # 가장 최단거리가 짧은 노드에 대한 정보 꺼내기
    dist, now = heapq.heappop(q)

    # 이미 처리된 노드였다면 무시
    # 별도의 visited 테이블이 필요없이 최단거리테이블을 이용해 방문여부 확인
    if distance[now] < dist:
      continue
    # 선택된 노드와 인접한 노드를 확인
    for i in graph[now]:
      cost = dist + i[1]
      # 선택된 노드를 거쳐서 이동하는 것이 더 빠른 경우
      if cost < distance[i[0]]:
        distance[i[0]] = cost
        heapq.heappush(q, (cost,i[0]))
  
#다익스트라 알고리즘수행
dijkstra(start)

count = 0
max_distance = 0

for d in distance:
  if d != INF:
    count += 1
    max_distance = max(max_distance, d)

## 시작노드는 제외해야함으로 count-1
print(count - 1, max_distance)

ps) 다익스트라 알고리즘 너무 어렵다...!!!ㅠㅠ