[BOJ][Python] 백준 14621번 - 나만 안되는 연애

문제 링크: https://www.acmicpc.net/problem/14621

14621번: 나만 안되는 연애

---

문제 풀이

최소 스패닝 트리를 이용하는 문제이다. 하지만 조건이 하나 추가 되었는데, 연결되어 있지 않은 간선을 유니온 시킬 때 둘다 남초 대학교 혹은 여초 대학교라면 유니온 시키지 않는다. 남자 - 여자 - 여자 - 남자 이렇게 연결 될 수도 있다 생각할 수 있는데 1번 조건에 따르면 불가능하다. 그 외에는 기본 최소 스패닝 트리이고 간선이 n-1개가 안된다면 -1을 출력해준다.

코드

	import sys
	sys.setrecursionlimit(10**9)
	input = sys.stdin.readline
	def find(p, x):
	if p[x] != x:
	p[x] = find(p, p[x])
	return p[x]
	def union(p, a, b):
	a = find(p, a)
	b = find(p, b)
	if a < b:
	p[b] = a
	else:
	p[a] = b
	n, m = map(int, input().split())
	schools = ['X'] + input().split()
	p = [i for i in range(n+1)]
	edges = []
	for _ in range(m):
	u, v, d = map(int, input().split())
	edges.append((d, u, v))
	edges.sort()
	result, lines = 0, 0
	for edge in edges:
	cost, a, b = edge
	if schools[a] != schools[b]:
	if find(p, a) != find(p, b):
	result += cost
	lines += 1
	union(p, a, b)
	if lines == n-1:
	break
	print(result if lines == n-1 else -1)

view raw 14621.py hosted with ❤ by GitHub