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

📌문제 탐색하기

• N(1≤ N ≤ 1,000)의 컴퓨터로 구성된 네트워크
  • 컴퓨터 중 몇 개는 서로 네트워크 연결이 되어있어 통신 가능 (양방향 통신)
  • 직접 연결되어 있는 회선 혹은 연결된 다른 컴퓨터를 거쳐서 통신 가능
• 각 컴퓨터와 회선은 성능이 차이가 남
  • 직접 연결되어 있는 회선을 사용할 경우 해당 회선을 이용해 통신하는 시간 만큼 소요
  • 여러 개의 회선을 거치는 경우 각 회선을 이용해 통신하는 시간의 합만큼 소요
• 해커가 네트워크에 침입하여, 보안 시스템을 단 한 개의 슈퍼컴퓨터, 1번 컴퓨터에만 설치하고자 함
  • 서로 다른 두 컴퓨터 간에 통신이 가능하되, 최소 개수의 회선만을 복구
  • 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는 데 걸리는 최소 시간이 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커지면 안됨
• 조건을 만족하면서 네트워크를 복구하는 방법을 알아내, 그 중 한 가지 방법에 대해 아래 내용 구하기
  • 복구할 회선의 개수
  • 복구한 회선이 연결하는 컴퓨터들

해당 문제는 각 컴퓨터들을 정점, 그리고 두 컴퓨터를 연결하는 회선을 노드, 통신에 걸리는 시간을 비용으로 생각하면 양의 가중치가 있는 양방향 그래프로 표현할 수 있다.

여기서 문제는 '어떻게 최소 개수의 회선만을 사용해서 1번 컴퓨터와 다른 모든 컴퓨터를 연결할 수 있을까?'다. 문제 조건에 의해서 슈퍼 컴퓨터가 다른 컴퓨터들과 통신하는 데 걸리는 최소 시간이 원래의 네트워크에서 통신하는 데 걸리는 최소 시간보다 커지면 안된다고 했으므로 원래의 네트워크에서 (1번 컴퓨터 - 다른 컴퓨터)가 통신하는 가장 빠른 방법의 경로(필요한 회선들)를 구해서 중복을 제거하면 될 것이라고 생각했다.

즉, 그래프의 특정 정점에서부터 시작해서 다른 정점까지 최소 비용으로 도달하는 경로를 구하는 문제이므로 다익스트라 알고리즘을 사용하여 해결할 수 있다.

 

📌코드 설계하기

1. 다익스트라 알고리즘을 구현할 함수 dijkstar(graph, start)를 정의한다.
   1. 1번 컴퓨터에서 각 컴퓨터까지의 최단 시간을 저장할 distances와 부모 노드를 저장할 parents를 생성하고, start번째 요소의 값은 0으로, distances의 나머지 요소들은 무한대(INF)로 초기화한다.
   2. 아직 방분하지 않은 정점 중에서 현재까지 계산된 최단 거리가 가장 작은 정점을 구하기 위해 우선순위큐 hq를 생성하고 (0, start)를 큐에 삽입한다.
   3. hq에 값이 존재하는 동안, hq에서 값을 꺼내서, 해당 정점과 연결된 다른 정점을 탐색하며 최소 비용 테이블 distances와 부모 노드 리스트 parents를 갱신한다.
   4. 최소 비용 테이블의 갱신이 종료된 후, parents를 반환한다.  
2. 컴퓨터의 개수 N, 회선의 개수 M을 입력받는다.
3. 컴퓨터의 연결 정보를 저장할 그래프 network를 생성하고, 회선의 정보를 입력받아 저장한다.
4. dijkstra(network, 1)을 실행하여 각 노드의 부모노드를 구해 parents에 저장한다.
5. 필요한 회선 개수(N-1)과 parents 리스트를 바탕으로 필요한 회선의 목록을 출력한다.

 

📌시도 회차 수정 사항

1회차

정답을 받았지만, 원래 작성한 코드에서 최단 경로의 간선을 구하는 부분에서 좀 더 간단한 로직이 있어 해당 부분을 수정했다.

원래 작성한 코드는 dijkstra 함수 내에서 ways 리스트를 사용해서 시작 노드부터 각 노드까지의 최단 경로 그 자체를 저장했다. 하지만 각 노드의 부모 노드만 저장하면 최단 경로를 복원할 수 있을 뿐만 아니라, 문제에서 필요한 것은 최단 경로에 사용되는 간선의 목록이었기 때문에 부모 노드를 저장하도록 바꿔서 코드를 간결하게 만들었다.

기존 코드

from heapq import heappush, heappop

import sys
input = sys.stdin.readline

def dijkstra(graph, start):
    hq = [(0, 1)]
    distances = [float('INF')]*(N+1)
    distances[start] = 0
    ways = [[] for _ in range(N+1)]
    
    while hq:
        cur_cost, cur_node = heappop(hq)
        
        if cur_cost > distances[cur_node]:
            continue
        
        for next_node, next_cost in graph[cur_node]:
            new_cost = distances[cur_node] + next_cost
            if new_cost < distances[next_node]:
                distances[next_node] = new_cost
                ways[next_node] = ways[cur_node] + [(cur_node,next_node)]
                heappush(hq, (new_cost, next_node))
        
    return ways

N, M = map(int, input().split())
network = [[] for _ in range(N+1)]
for _ in range(M):
    a, b, c = map(int, input().split())
    network[a].append((b, c))
    network[b].append((a, c))

ways = dijkstra(network, 1)

lines = set()
for way in ways:
    for line in way:
        lines.add(line)

print(len(lines))
for a, b in lines:
    print(a, b)

 

 

📌정답 코드

from heapq import heappush, heappop

import sys
input = sys.stdin.readline

def dijkstra(graph, start):
    hq = [(0, 1)]
    distances = [float('INF')]*(N+1)
    distances[start] = 0
    parents = [0]*(N+1)
    
    while hq:
        cur_cost, cur_node = heappop(hq)
        
        if cur_cost > distances[cur_node]:
            continue
        
        for next_node, next_cost in graph[cur_node]:
            new_cost = distances[cur_node] + next_cost
            if new_cost < distances[next_node]:
                distances[next_node] = new_cost
                parents[next_node] = cur_node
                heappush(hq, (new_cost, next_node))
        
    return parents


N, M = map(int, input().split())
network = [[] for _ in range(N+1)]
for _ in range(M):
    a, b, c = map(int, input().split())
    network[a].append((b, c))
    network[b].append((a, c))

parents = dijkstra(network, 1)

print(N-1)
for i in range(2, N+1):
    print(i, parents[i])