[백준 2211번] 파이썬 - 네트워크 복구

백준 2211 - 네트워크 복구

시간 제한 2초, 메모리 제한 192MB

# 조건

• N(1 ≤ N ≤ 1,000)개의 컴퓨터로 구성된 네트워크가 있다.
• 이들 중 몇 개의 컴퓨터들은 서로 네트워크 연결이 되어 있어 서로 다른 두 컴퓨터 간 통신이 가능하도록 되어 있다.
• 통신을 할 때에는 서로 직접 연결되어 있는 회선을 이용할 수도 있으며, 회선과 다른 컴퓨터를 거쳐서 통신을 할 수도 있다.
• 각 컴퓨터들과 회선은 그 성능이 차이가 날 수 있다.
  • 따라서 각각의 직접 연결되어 있는 회선을 이용해서 통신을 하는데 걸리는 시간이 서로 다를 수 있다.
  • 심지어는 직접 연결되어 있는 회선이 오히려 더 느려서, 다른 컴퓨터를 통해서 통신을 하는 것이 더 유리할 수도 있다.
• 직접 연결되어 있는 회선을 사용할 경우에는 그 회선을 이용해서 통신을 하는 데 드는 시간만큼이 들게 된다.
  • 여러 개의 회선을 거치는 경우에는 각 회선을 이용해서 통신을 하는 데 드는 시간의 합만큼의 시간이 걸리게 된다.
• 어느 날, 해커가 네트워크에 침입하였다.
• 네트워크의 관리자는 우선 모든 회선과 컴퓨터를 차단한 후, 해커의 공격을 막을 수 있었다.
• 관리자는 컴퓨터에 보안 시스템을 설치하려 하였는데, 버전 문제로 보안 시스템을 한 대의 슈퍼컴퓨터에만 설치할 수 있었다.
  • 한 컴퓨터가 공격을 받게 되면, 네트워크를 통해 슈퍼컴퓨터에 이 사실이 전달이 되고, 그러면 슈퍼컴퓨터에서는 네트워크를 이용해서 보안 패킷을 전송하는 방식을 사용하기로 하였다.
• 준비를 마친 뒤, 관리자는 다시 네트워크를 복구하기로 하였다.
• 이때, 다음의 조건들이 만족되어야 한다.
  1. 해커가 다시 공격을 할 우려가 있기 때문에, 최소 개수의 회선만을 복구해야 한다. 물론, 그렇다면 아무 회선도 복구하지 않으면 되겠지만, 이럴 경우 네트워크의 사용에 지장이 생기게 된다. 따라서 네트워크를 복구한 후에 서로 다른 두 컴퓨터 간에 통신이 가능하도록 복구해야 한다.
  2. 네트워크를 복구해서 통신이 가능하도록 만드는 것도 중요하지만, 해커에게 공격을 받았을 때 보안 패킷을 전송하는 데 걸리는 시간도 중요한 문제가 된다. 따라서 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다.
• 원래의 네트워크에 대한 정보가 주어졌을 때, 위의 조건을 만족하면서 네트워크를 복구하는 방법을 알아내는 프로그램을 작성하시오.

입력

• 첫째 줄에 두 정수 N, M이 주어진다.
• 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다.
• 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다는 의미이다.
• 컴퓨터들의 번호는 1부터 N까지의 정수이며, 1번 컴퓨터는 보안 시스템을 설치할 슈퍼컴퓨터이다.
• 모든 통신은 완전쌍방향 방식으로 이루어지기 때문에, 한 회선으로 연결된 두 컴퓨터는 어느 방향으로도 통신할 수 있다.

출력

• 첫째 줄에 복구할 회선의 개수 K를 출력한다.
• 다음 K개의 줄에는 복구한 회선을 나타내는 두 정수 A, B를 출력한다.
• 이는 A번 컴퓨터와 B번 컴퓨터를 연결하던 회선을 복구한다는 의미이다.
• 출력은 임의의 순서대로 하며, 답이 여러 개 존재하는 경우에는 아무 것이나 하나만 출력하면 된다.

# 접근 방법

• 문제 설명이 길지만 요약하자면 1번 컴퓨터에서 시작하여 최소의 비용으로 모든 컴퓨터를 순회하면 되는 것이다.
• 음의 가중치가 없으므로 다익스트라를 이용해주어도 충분히 풀 수 있는 문제이다.
• dist 배열은 충분히 큰 값으로 N+1 크기로 만들어주고 1번 컴퓨터를 0으로 초기화해준다.
• 경로도 함께 출력해주어야 하므로 parents 배열도 만들어준다.
• heapq를 이용하여 걸리는 시간이 적은 순으로 heappush를 해줄건데 heappop을 하였을 때, 현재 누적된 시간이 기록된 값 보다 크다면 continue
• 또한, 다음 노드를 탐색하며 현재 누적 시간 + 더해질 시간이 기록된 시간보다 작다면 갱신해주고 heappush 해준다.
  • 이 때 더 작은 값으로 갱신되었다면 연결된 node를 parents배열에서 함께 갱신시켜준다.
• 출력 형식을 잘 확인하지 않아서 시간을 잡아먹었다.
  • 복구에 필요한 총 시간이 아닌, 복구를 할 총 회선 수를 출력하는 것이었다...

import sys  
input = sys.stdin.readline  
from heapq import heappop, heappush  

def djikstra():  
    q = [(0, 1)]  
    while q:  
        val, now = heappop(q)  
        if val > dist[now]:  
            continue  

        for w, node in graph[now]:  
            n_val = val + w  
            # 더 적은 시간으로 갱신해주기  
            # 이 때, 연결된 노드도 변경해준다.            
            if dist[node] > n_val:  
                dist[node] = n_val  
                heappush(q, (n_val, node))  
                parents[node] = now  

N, M = map(int, input().split())  
graph = [[] for _ in range(N+1)]  
for _ in range(M):  
    a, b, c = map(int, input().split())  
    graph[a].append((c, b))  
    graph[b].append((c, a))  
dist = [float('inf')] * (N+1)  
dist[1] = 0  
parents = [0] * (N+1)  
djikstra()  
print(N-1)  
for i in range(2, N+1):  
    print(i, parents[i])