[Algorithm] BAEKJOON 2211번. 네트워크 복구

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

• 문제명 : 네트워크 복구
• 사용언어 : python
• 알고리즘 : Dijkstra(다익스트라) 알고리즘, 최단경로

---

  문제

N(1 ≤ N ≤ 1,000)개의 컴퓨터로 구성된 네트워크가 있다. 이들 중 몇 개의 컴퓨터들은 서로 네트워크 연결이 되어 있어 서로 다른 두 컴퓨터 간 통신이 가능하도록 되어 있다. 통신을 할 때에는 서로 직접 연결되어 있는 회선을 이용할 수도 있으며, 회선과 다른 컴퓨터를 거쳐서 통신을 할 수도 있다.

각 컴퓨터들과 회선은 그 성능이 차이가 날 수 있다. 따라서 각각의 직접 연결되어 있는 회선을 이용해서 통신을 하는데 걸리는 시간이 서로 다를 수 있다. 심지어는 직접 연결되어 있는 회선이 오히려 더 느려서, 다른 컴퓨터를 통해서 통신을 하는 것이 더 유리할 수도 있다. 직접 연결되어 있는 회선을 사용할 경우에는 그 회선을 이용해서 통신을 하는 데 드는 시간만큼이 들게 된다. 여러 개의 회선을 거치는 경우에는 각 회선을 이용해서 통신을 하는 데 드는 시간의 합만큼의 시간이 걸리게 된다.

어느 날, 해커가 네트워크에 침입하였다. 네트워크의 관리자는 우선 모든 회선과 컴퓨터를 차단한 후, 해커의 공격을 막을 수 있었다. 관리자는 컴퓨터에 보안 시스템을 설치하려 하였는데, 버전 문제로 보안 시스템을 한 대의 슈퍼컴퓨터에만 설치할 수 있었다. 한 컴퓨터가 공격을 받게 되면, 네트워크를 통해 슈퍼컴퓨터에 이 사실이 전달이 되고, 그러면 슈퍼컴퓨터에서는 네트워크를 이용해서 보안 패킷을 전송하는 방식을 사용하기로 하였다. 준비를 마친 뒤, 관리자는 다시 네트워크를 복구하기로 하였다. 이때, 다음의 조건들이 만족되어야 한다.

해커가 다시 공격을 할 우려가 있기 때문에, 최소 개수의 회선만을 복구해야 한다. 물론, 그렇다면 아무 회선도 복구하지 않으면 되겠지만, 이럴 경우 네트워크의 사용에 지장이 생기게 된다. 따라서 네트워크를 복구한 후에 서로 다른 두 컴퓨터 간에 통신이 가능하도록 복구해야 한다.
네트워크를 복구해서 통신이 가능하도록 만드는 것도 중요하지만, 해커에게 공격을 받았을 때 보안 패킷을 전송하는 데 걸리는 시간도 중요한 문제가 된다. 따라서 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다.
원래의 네트워크에 대한 정보가 주어졌을 때, 위의 조건을 만족하면서 네트워크를 복구하는 방법을 알아내는 프로그램을 작성하시오.

 

 

  알고리즘 및 실행 코드

먼저, Dijkstra(다익스트라) 알고리즘에 대해 정리해보자.

다익스트라 알고리즘은 그래프 알고리즘에서 '최소 비용'을 구해야 하는 경우 유용하게 사용되는 알고리즘이다.

최소 비용 중에서도, 주어진 두 노드(시작노드, 도착노드) 사이에 최소 비용인 경로를 찾을 때 유용하게 사용된다.

 

 

Dijkstra 알고리즘

시작점의 distance를 0으로, predecessor를 None으로

모든 노드가 complete 일 때까지:

    complete하지 않은 노드 중 distance가 가장 작은 노드 선택

    이 노드에 인접한 노드 중 complete하지 않은 노드를 돌면서:

        각 엣지를 relax한다

    현재 노드를 complete 처리한다

 

 

문제 요약 -> 슈퍼 컴퓨터를 추가함으로써 필요 없는 회선은 줄이고 새로운 네트워크 구축.

위 Dijkstra 알고리즘을 사용하여 각 노드 간 연결비용을 최소화하고, 회선의 개수도 최소화하기.

 

 

▼실행코드

import sys
import heapq

input = sys.stdin.readline
INF = int(1e9)    # 무한대를 표현할 변수 INF 설정


def dijkstra(start):
  q = []
  distance[start] = 0
  heapq.heappush(q, (0, start))

  while q:
    dist, now = heapq.heappop(q)   # 가장 거리가 짧은 노드 선택

    if distance[now] < dist:       # 이미 처리된 노드는 스킵
      continue

    for next_node, next_cost in graph[now]:
      # 현재 노드와 연결된 노드들에 대해
      # 시작 노드에서 현재 노드까지의 거리에 연결된 노드까지의 거리를 더함
      cost = dist + next_cost

      if distance[next_node] > cost:
        # 기존에 저장된 거리보다 새로 계산된 거리가 더 짧다면
        # 부모노드를 현재 노드로 갱신하고 거리를 갱신
        parent[next_node] = now
        distance[next_node] = cost
        
        # 우선순위 큐에 추가하여 다음 노드로 탐색 진행
        heapq.heappush(q, (cost, next_node))


n, m = map(int, input().split())

distance = [INF] * (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))

dijkstra(1)   # 다익스트라 알고리즘을 시작 노드를 1로 하여 실행

print(n - 1)
for i in range(2, n + 1):
  print(i, parent[i])