[python] 백준 - 1922. 네트워크 연결

문제 해결

1. 오늘 배운 최소 신장 트리(MST)를 사용하는 그래프 문제다. ( + heapq 모듈 사용 )

💨 그래프에서 사이클을 제거하고 모든 노드를 포함하는 트리를 구성할 때, 가중치의 합이 최소가 되도록 만든 경우를 최소신장트리라고 한다.

 (1) 먼저 간선과 가중치를 인접리스트로 만든다.

 (2) key, mst, pq | 최소 가중치를 갱신하는 배열, 방문 배열, 힙큐( 최소값을 뽑는 모듈 )

2. 시작점( 노드중 아무거나 )을 힙큐에 넣어주고 시작 - 이 문제에서는 모든 노드를 연결할 수 있다.

 (1) 힙큐 안에서 가중치가 가장 낮은 정점을 pop

 (2) 방문했는지 확인 | 이미 방문을 했다면 continue 를 통해 힙큐에서 다시 뽑고, 아니라면 True로 바꿔주고 가중치를 결과에 더해준다.

 (3) 인접리스트를 통해 현재 정점에서 갈 수 있으며 아직방문을 안했고, 가중치가 현재 key배열에 있는 가중치보다 작으면 key값을 갱신하고, 힙큐에 넣어준다.

 

-> 인접행렬을 사용했다. - 시간초과 - 인접리스트 사용

처음 시작 노드마다 값이 다른줄 알고 for문을 통해 모든 노드를 시작점으로 돌려줬다. - 시간초과

 

+ 자주 나오는 개념은 아니지만 알아두면 좋을 것 같다. 

처음 배운 개념이라 배운 코드와 내용이 다르면 잘 이해가 가지 않는다.

근데 다른코드가 효율이 더 좋아보인다.....😭

 

소스 코드

import heapq
n,  m = int(input()), int(input())

# 인접리스트
adj = {i: [] for i in range(n)}
for _ in range(m):
    s, e, c = map(int, input().split())
    adj[s-1].append([e-1, c])
    adj[e-1].append([s-1, c])

# key : 가장 큰 값들로 채움(최소값을 이용할 것이기 때문) | key는 인덱스번호인 정점에서 갈 수 있는 최소 가중치
# mst : visit과 비슷한 개념
# pq : 힙큐 모듈 사용 - heapq.heappop 사용시 최소값이 나온다. - 시간복잡도 good
key = [float('inf')] * n
mst = [False] * n
pq = []

# 시작 점을 정해주고 | 여기서는 아무 정점이나 정해준다. 시작점에서 시작점으로 가는 key 는 0
key[0] = 0
heapq.heappush(pq, (0, 0))
result = 0

while pq:
    k, u = heapq.heappop(pq)  # 가중치가 최소인 정점을 뽑아주고

    if mst[u]:  # 힙큐에 이미 방문한 정점도 포함되어 있으므로, 이미 방문한 정점이 나오면 스킵!
        continue

    mst[u] = True  # 잘뽑았으면 방문 표시
    result += k  # 결과에 가중치를 더해준다.

    for dest, w in adj[u]:  # u 에서 갈 수 있는 곳을 찾아
        if not mst[dest] and w < key[dest]:  # 아직방문하지 않은 곳이면서 key에 저장된 가중치보다 작은 값이라면
            key[dest] = w  # key값을 갱신
            heapq.heappush(pq, (key[dest], dest))  # 힙큐에 다음 목적지를 저장

print(result)

 

출처 : BACKJOON ONLINE JUDGE

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

1922번: 네트워크 연결