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

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

최소 스패닝 트리 문제로 크루스칼 알고리즘으로 접근했습니다.

2) 알고리즘

• 크루스칼

3) 풀이 코드

사용 언어 - Python

def find_set(x):                    # 정점 x 의 최상단 정점을 찾음
    if x != s[x]:
        s[x] = find_set(s[x])
    return s[x]


def union(x, y):                    # 두개의 집합을 서로 합침
    s[find_set(y)] = find_set(x)


def kruskal():                              # 크루스칼 알고리즘
    global answer 

    edge_cnt, idx = 0, 0                    # 모두 연결이 되었는지 확인을 위한 변수, 간선 집합의 인덱스 번호

    while edge_cnt != V-1:                  # 정점-1 개 만큼 연결되어 있지 않으면
        x = linked[idx][0]                  # 두개의 정점
        y = linked[idx][1]

        while find_set(x) != find_set(y):   # 두개가 연결되어 있지 않으면
            union(x, y)                     # 연결
            edge_cnt += 1                   # 연결 개수 증가
            answer += linked[idx][2]        # 정답 증가
        idx += 1                            # 간선 인덱스 증가


V, E = map(int, sys.stdin.readline().split())       # 정점의 개수, 간선의 개수

s = [x for x in range(V+1)]                         # 정점들이 연결되었는지 확인을 위한 집합
linked = sorted([list(map(int, sys.stdin.readline().split())) for _ in range(E)], key=lambda x: x[2])       # 연결 관계
answer = 0

kruskal()   
print(answer)

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

- https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다