[백준] 1197 최소 스패닝 트리.py

pseeej·2021년 8월 12일

Algorithms MST baekjoon kruskal

문제 링크 : https://acmicpc.net/problem/1197

💡 아이디어

문제를 어떤 방식으로 해결하려 했는지 그 과정을 적어주세요. 초기에 접근한 방법과 최종 접근이 차이가 없으면 한개만 적어도 됩니다.

최종 접근

처음에 강의 듣고 C++로 하려다가,,, 집합을 어떻게 해야할지 모르겠어서,,, 검색해보니깐 vector로 합치는 방법,,, 뭐 이런 게 있던데 걍 다 건너뛰고 python으로 넘어왔당ㅋ 키키 이럴 때 파이썬 쓰는 거 아니겠어~^^
처음에 다 입력받는데,,, 연결되어있는 node랑 그 사이 거리 입력받고 나서는 tuple 형태로 해서 v_list라는 곳에 넣어줬다. 그러고 그거를 이제 거리 기준으로 정렬해주고... 그 다음엔 sets라는 list에다가 모든 node에 대한 집합?을 넣어줬다. 다음으로는 v_list를 하나씩 탐색하면서,,, 연결되어있는 두 노드가 같은 위치의 집합에 들어있는지 확인해줬다. 만약 같은 위치가 아니라면! 각각이 들어가있는 집합을 합쳐주고, 최종 결과에 거리를 더해주고...

📋 사용 스펙

어떤 알고리즘 또는 기법을 사용해 문제를 해결했는지 알려주세요

최소 스패닝 트리(MST)
집합

👨🏻‍💻 👩‍💻 코드

V, E = map(int, input().split())

v_list = [] # (ver1, ver2, len)
for i in range(E):
    a, b, c = map(int, input().split())
    v_list.append((a, b, c))

# 거리 기준으로 정렬
v_list = sorted(v_list, key = lambda vertex:vertex[2])

# 집합? 형태로 저장해둘 배열
sets = []
for i in range(V):
    sets.append([i+1])

# v_list 돌면서 연결되어있는 두 노드가 같은 위치의 집합에 있는지 확인
res = 0
for vertex in v_list:
    first, second, dist = vertex
    flag = True
    for s in range(len(sets)):
        # 같은 위치에 있으면 그냥 넘기고 (순환?되면 안되니깐!)
        if first in sets[s] and second in sets[s]:
            flag = False
            continue
        
        # 다른 위치에 있으면 각각의 위치 기록해줌
        if first in sets[s]:
            first_index = s
        if second in sets[s]:
            second_index = s

    # 각 노드가 들어가있던 거 하나로 합쳐주기
    if flag == True:
        sets[first_index] += sets[second_index]
        sets.pop(second_index)
        res += dist

    # 모든 노드들이 하나의 배열에 다 들어가있따면 종료
    if len(sets[0]) == V:
        break

print(res)