[백준 2024/02/13] 1922번 네트워크 연결

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

1922번: 네트워크 연결

 

1. 접근 방법

이번 문제는 최소 신장 트리를 이용할 수 있는 대표적인 문제였다. 

나는 이번에 Prim's Algorithm 을 이용해서 이번 문제에 접근하였다.

아직은 Kruskal's Algorithm 보다 Prim's Algorithm이 접근하기 쉽게 느껴졌기 때문이다.

 

<Prim's Algorithm>

1) 임의의 정점을 시작으로 선택한다. 최소 신장 트리의 첫 번째 정점이 된다.

2) edge 선택. 선택된 정점들과 연결된 edge 중에서 가장 가중치가 낮은 edge를 선택하고, 이 edge가 연결되는 정점을 최소 신장 트리에 추가한다. 이때, 이미 접근한 정점은 선택하지 않아야 한다.

3) 모든 정점이 최소 신장 트리에 포함될 때까지 반복한다. 

 

<시각화하여 알아보자>

node_list = [[] for _ in range(n+1)]

for i in range(m):
    start, end, w = map(int, input().split())
    node_list[start].append((w, end))
    node_list[end].append((w, start))

위 코드를 통해서, 간선과 노드들을 정리해주었다.

1 2 5 를 예로 들어보면, 1번 노드 - 2번 노드 가 연결되는 간선이고 가중치는 5이다.

이때,

node_list[1].append(5, 2)

node_list[2].append(5, 1)

을 해준 것이다. 두 방향 다 왔다갔다가 가능하므로, 이렇게 두 개를 넣어주었다.

 

#1번 노드 [(5, 2), (4, 3)]
#2번 노드 [(5, 1), (2, 3), (7, 4)]
#3번 노드 [(4, 1), (2, 2), (6, 4), (11, 5)]
#4번 노드 [(7, 2), (6, 3), (3, 5), (8, 6)]
#5번 노드 [(11, 3), (3, 4), (8, 6)]
#6번 노드 [(8, 4), (8, 5)]

 

이런식으로  node_list가 구성되게 된다.

 

이제 1번 노드를 임의의 노드로 선택해서 넓혀나갈 것이다.

 

그렇다면, heap ( 갈 수 있는 간선들을 포함하는 곳) 에다가 1번 노드 값들을 넣어줄 것이다.

weight 의 경우 idx 보다 앞에 들어가야 한다. 그래야지, heap에서 weight를 기준으로 최소 힙으로 정렬할 수 있기 때문이다.

for (weight, idx) in node_list[1]:
    heapq.heappush(heap, (weight, idx))

 

또한 1번 노드를 방문 했음을 체크해서, 다음에 또 1번 노드를 방문하지 않도록 해야한다. 왜냐하면, 다시 방문할 시, 싸이클이 생길 수 있기 때문이다.

visited = [False] * (n+1)
visited[1] = True

 

visited list를 만들어서 체크하도록 하였다.

 

이후 while 문을 돌기 시작한다.

먼저 heapq.heappop 을 통해서, 가중치가 가장 작은 값을 가지고 오게 된다. 만약 visited에 들어가 있는 idx라면 continue를 해주었고, 아니라면 해당 값의 weight를 더해주었다.

 

이후 새로 접근한 노드 (idx) 번호에 대해서, 해당 번호에서 접근할 수 있는 간선들을 heap 에다가 모두 넣어주었다.

이렇게 넣어주게 된다면, 이전에 접근했던 노드에서 갈 수 있는 곳들과, 현재 새로 접근한 노드 번호에 대해서 갈 수 있는 곳들이 모드 heap에 들어가 있게 된다. 

 

heap에서 현재 접근한 노드들 중, 가장 weight이 작은 간선을 뽑아주게 되는 것이다.

for weight, idx in node_list[idx]:
    heapq.heappush(heap, (weight, idx))

 

2. 코드

import heapq

n = int(input())
m = int(input())
node_list = [[] for _ in range(n+1)]
visited = [False] * (n+1)
heap = []
answer = 0
edges = 0

for i in range(m):
    start, end, w = map(int, input().split())
    node_list[start].append((w, end))
    node_list[end].append((w, start))


for (weight, idx) in node_list[1]:
    heapq.heappush(heap, (weight, idx))

visited[1] = True

while edges < n-1:
    weight, idx = heapq.heappop(heap)
    if visited[idx]:
        continue
    visited[idx] = True
    answer += weight
    edges += 1

    for weight, idx in node_list[idx]:
        heapq.heappush(heap, (weight, idx))

print(answer)