[백준] 2211번 - 네트워크 복구 / 골드 2 / 파이썬 풀이

문제 링크

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

 

시간 제한 : 2초

메모리 제한 : 192 MB

 

문제 요약

• N개의 컴퓨터로 이루어진 네트워크가 있다. (입력으로 주어짐)
• 각 컴퓨터는 직접 연결되어 있을 수도 있고, 다른 컴퓨터를 거쳐서 연결되어 있을 수도 있는데,
  이때 통신에 걸리는 시간은 직접 연결 = 회선에 대한 시간, 간접 연결 = 각 회선의 대한 시간의 합이 된다.
• M개의 회선간 정보가 입력으로 주어짐
  (세 개의 정수 A B C 형태로 주어지는 데, A회선-B회선 간의 통신 시간이 C 이다.)
• 해커가 네트워크에 침입을 해서, 모든 회선과 컴퓨터를 차단한 상태에서 시작을 한다.
• 네트워크 관리자가 네트워크를 복구해야 하는데, 다음 두 가지 조건이 있다.
  1) 해커 재공격 우려 때문에, 서로 다른 두 컴퓨터 간의 통신이 되도록(모든 컴퓨터) 최소 개수의 회선만 복구한다.
  2) 슈퍼컴퓨터와 다른 컴퓨터의 통신 최소 시간 < 원래의 네트워크에서의 통신 최소 시간
  
  
• 문제 : 위 두 조건을 만족하는, 네트워크를 복구하는 프로그램 작성.
  
  
• 종료 조건
  - 블라블라~
  - 블라블라~

 

입력

4 5
1 2 1
1 4 4
1 3 2
4 2 2
4 3 3

 

출력

3
1 2
3 1
4 2

---

풀이

"슈퍼 컴퓨터를 넣음으로써, 쓸모 없는 회선을 버리고, 새로운 네트워크를 구축하겠다
=> 다익스트라로 각 노드 간의 연결비용을 최소화 하고, 회선 개수도 최소화하자!"

import sys
import heapq


input = sys.stdin.readline
INF = int(1e9)  # 다익스트라 적용시키기 위한 무한대 설정

n, m = map(int, input().split()) # N, M 입력 받음.
node_cost = [INF] * (n + 1) # 각 노드(컴퓨터)간의 연결된 회선 통신 비용 초기화. n+1은 인덱스랑 주어진 숫자랑 맞춰주기 위함.
parent = [0] * (n + 1)

graph = [[] for _ in range(n + 1)]  # 입력으로 주어지는 간선 비용 정보 설정 위함.
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))


def dijkstra(start):
    q = []
    node_cost[start] = 0
    heapq.heappush(q, (0, start))   # q라는 배열(힙 구조)에 (회선 통신비용, 노드번호) 형태로 넣겠다.

    while q:
        q_cost, now_node = heapq.heappop(q)

        if node_cost[now_node] < q_cost:    # 이미 연결되어 있는 노드의 비용이 현재 큐에서 꺼낸 비용보다 더 작다면,
            continue    # 회선 비용 정보를 재정의할 필요가 없음.

        for connected_node_num, connected_node_cost in graph[now_node]:
            current_cost = q_cost + connected_node_cost     # 비교대상이 되는 현재의 회선 통신비용

            if node_cost[connected_node_num] > current_cost:    # 현재 비교하는 간선의 통신비용이 더 작다면
                parent[connected_node_num] = now_node
                # parent는 최종적으로 연결시켜야만 하는 노드의 번호를 저장하기 위함.
                # 더 짧은 비용으로 갱신될 때마다 parent도 함께 갱신.
                node_cost[connected_node_num] = current_cost
                # 연결되어 있는 노드와 통신하는 비용을 재정의. (최소화)
                heapq.heappush(q, (current_cost, connected_node_num))
                # 현재 노드와 연결되어 있는 다음 노드로 넘어가서 비교하기 위해 다시 큐에 추가.


dijkstra(1)     # 노드 번호 1부터 시작.

print(n - 1)    # 모든 노드를 연결시키기 위해 필요한 최소 회선 수
for i in range(2, n+1):
    print(i, parent[i])

 

참고

https://bbbyung2.tistory.com/85

[Python] [백준] 2211번: 네트워크 복구

https://m.blog.naver.com/ndb796/221234424646 - 다익스트라 알고리즘이란?

23. 다익스트라(Dijkstra) 알고리즘