[백준 1922번 골드4/PY] 네트워크 연결

문제 출처

백준 - 1922번

나의 풀이

크루스칼 알고리즘

• 비용을 기준으로 정렬을 해주고
• 순회하면서 부모가 같지 않으면 합쳐주고 비용을 계산한다.

import sys

# sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n = int(input())
m = int(input())


def getParent(parent, x):
    if parent[x] != x:
        parent[x] = getParent(parent, parent[x])
    return parent[x]


def unionParent(parent, a, b):
    a = getParent(parent, a)
    b = getParent(parent, b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b


result = 0

parent = [0] * (n + 1)
for i in range(n + 1):
    parent[i] = i


line = []
for _ in range(m):
    a, b, cost = map(int, input().split())
    line.append((cost, a, b))

line.sort()

for check in line:
    cost, a, b = check
    if getParent(parent, a) != getParent(parent, b):
        unionParent(parent, a, b)
        result += cost

print(result)

크루스칼 알고리즘

18. 크루스칼 알고리즘(Kruskal Algorithm) : 네이버 블로그
[Python] 최소 신장 트리를 찾는 크루스칼(Kruskal) 알고리즘

크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 비용 신장 트리를 만들기 위한 대표적인 알고리즘이다.

크루스칼 알고리즘의 핵심 개념은, 거리가 짧은 순서대로 간선 정보를 정렬하고 비용이 적은 간선부터 그래프에 포함시키면 된다는 것이다.

신장 트리란, 하나의 그래프가 있을 때 모든 노드를 포함하면서, 즉 모든 노드들 간에 서로 연결은 되어 있되, 사이클이 존재하지 않는 부분 그래프를 말한다.

파이썬 리스트 정렬

sort()는 원본 리스트 정렬 
sorted()는 새로 정려된 리스트 반환

숫자리스트.sort() => 음수, 0, 양수 순
소문자리스트.sort() => 알파벳 순 
대소문자리스트.sort() => 대문자, 소문자 순 (왜냐면 문자를 아스키코드로 판단하기 때문, A-Z는 65~90, a-z는 97~122이므로)

내림차순하려면 
sort(reverse=True)

파이썬 튜플?

튜플

리스트는 []를 사용하는 반면, 튜플은 ()를 사용한다.
리스트는 리스트 내 원소를 변경할 수 있지만, 튜플은 불가능하다.

튜플은 리스트보다 빠르다. 한번 저장한 데이터를 수정하거나 삭제할 일이 없으면 튜플을 쓰는 게 좋다.

튜플도 리스트와 비슷하게 인덱싱을 통해 원소에 접근할 수 있다.

튜플도 리스트와 비슷하게 슬라이싱이 가능하다.

t = ('Samsung', 'LG', 'SK')

print(t[0:2])  # ('Samsung', 'LG')