[Python] 백준 14621 나만 안되는 연애 | 크루스칼 알고리즘

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

https://www.acmicpc.net/problem/14621

14621번: 나만 안되는 연애

 

 

문제 해결 포인트

- 크루스칼 알고리즘 문제

 

- school : 정점 별 학교 성별

- parent : 정점 별 서로소 집합 정보

- edges : 간선의 비용 기준으로 오름차순 정보 저장

 

- 정렬된 edges를 순차적으로 접근하며 사이클이 발생하지 않으면 연결

- 서로소 집합이 정점 본인과 같은 정점의 개수를 세어서 1개 이상이라면 집합이 1개 이상이라는 의미

   - 모든 정점을 연결할 수 없다는 의미와 같으므로 -1 반환

   -  그렇지 않다면 간선의 최소 비용 반환

 

 

작성 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
school = [''] + list(input().split())
parent = [i for i in range(n+1)]
edges = []
result = 0

for _ in range(m):
    u, v, d = map(int, input().split())
    edges.append((d, u, v))

edges.sort()

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

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

for w, a, b in edges:
    if find(a) != find(b) and school[a] != school[b]:  # 사이클 발생하지 않고, 여초/ 남초로 다르다면
        union(a, b)
        result += w

print(result if len([i for i in range(1, n+1) if parent[i] == i]) == 1 else -1)

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚