백준 18769 : 그리드 네트워크 (Python)

본문 링크

import sys
input=sys.stdin.readline

def Find(x):

    if x!=disjoint[x]:
        disjoint[x]=Find(disjoint[x])
    return disjoint[x]

for i in range(int(input())):

    R,C=map(int,input().split())

    edge=[] ; Node=1 ; disjoint=[ _ for _ in range(R*C+1) ]
    for j in range(R):
        R_list=list(map(int,input().split()))

        for k in range(len(R_list)):

            edge.append((R_list[k] , Node , Node+1))
            Node+=1
        Node+=1

    Node=1
    for j in range(R-1):

        C_list=list(map(int,input().split()))

        for k in range(len(C_list)):

            edge.append((C_list[k] , Node , Node+C) )
            Node+=1


    edge.sort(key=lambda x:x[0]) ; total=0

    for value,x,y in edge:

        x=Find(x)
        y=Find(y)

        if x!=y:
            if x>y:
                disjoint[x]=y
            else:
                disjoint[y]=x
            total+=value
    print(total)

📌 어떻게 접근할 것인가?

문제 입력받는게 좀 까다로웠다.

• 1 2 3
  4 5 6
  7 8 9

위 형식으로 노드 번호를 만들었고 서로 연결되는 간선을 입력받았습니다.

이후 그냥 크루스칼 알고리즘을 통해서 최소스패닝 트리를 만들어 주었습니다.

입력만 잘 받으면 쉽게 풀리는 문제입니다.