Skip to main content

1922 - 네트워크 연결

info
  • 문제 보기: 1922 - 네트워크 연결
  • 소요 시간: 12분 54초
  • 풀이 언어: python
  • 체감 난이도: 2️⃣
  • 리뷰 횟수: ✅

풀이 키워드​

스포주의

그래프 최소스패닝트리 유니온파인드


풀이 코드​

info
  • 메모리: 47528 KB
  • 시간: 216 ms
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

parent = []

def union(a, b):
    global parent
    
    pa = find(a)
    pb = find(b)
    
    if pa < pb:
        parent[pb] = pa
    else:
        parent[pa] = pb
    

def find(x):
    global parent
    
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]


def solution():
    global parent
    
    n = int(input())
    m = int(input())
    parent = [x for x in range(n+1)]
    tree = []
    for _ in range(m):
        a, b, weight = map(int, input().split())
        tree.append((weight, a, b))
        
    # Kruskal
    ans = 0
    tree.sort()
    for data in tree:
        weight, a, b = data
        if find(a) != find(b):
            ans += weight
            union(a, b)
            
    print(ans)


if __name__ == '__main__':
    solution()

풀이 해설​

MST 문제이므로, 크루스칼 알고리즘을 사용하면 된다.

Kruskal 알고리즘의 설명은
최소 스패닝 트리 풀이 내용으로 대체한다.

메모​

  • 이전에 MST 기본 문제 풀었어서 체감 난이도가 한단계 더 낮아짐
  • tree 리스트의 네이밍을 graph로 변경하는 것이 나을 것 같다는 생각...?
  • union 알고리즘 구현 계속 실수하고 있음; 😦
    • 제발 parent 끼리 연산하시라고요
    • 제발 좀