[파이썬] 백준 16402 : 제국 (골드2)

[파이썬] 백준 16402 : 제국 (골드2)

• https://www.acmicpc.net/problem/16402

---

풀이

방향성 생각

• 유니온 파인드
• 서로 다른 군집끼리 진행했을 때는, 이긴 쪽 루트를 루트로 설정해주면 된다.
• 서로 같은 군집끼리 진행했을 때는, 부모가 해당 루트인 모든 노드들을 이긴 노드로 변경한다.
• N이 매우 작게 나왔는데, 문제 의도는 매 쿼리마다 경로압축으로 루트를 업데이트하는 문제인듯?

 

---

전체코드

import sys

input = lambda : sys.stdin.readline().strip()

def get_name(string):
    return string.split()[-1]

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

N,M = map(int,input().split())

# 이름 -> 숫자, 숫자 -> 이름
cvt = {}
cvt_rev = {}
for i in range(N):
    _, _, name = input().split()
    cvt[name] = i
    cvt_rev[i] = name

P = [val for val in cvt.values()]
for _ in range(M):
    kingdom1, kingdom2, w = input().split(',')
    name1, name2 = get_name(kingdom1), get_name(kingdom2)

    x,y = cvt[name1], cvt[name2]
    px,py = find(x), find(y)

    # 다른 군집이면 이긴쪽 루트로 유니온 파인드드
    if px != py:
        if w == '1':
            P[py] = px
        else:
            P[px] = py

    # 같은 군집이면 px, py 중 하나는 부모일텐데 전체 배열을 순회하면서 같은 군집을 이긴쪽 노드로
    else:
        if w == '1':
            P[x] = x
            for i in range(N):
                if find(i) == py:
                    P[i] = x
        else:
            P[y] = y
            for i in range(N):
                if find(i) == px:
                    P[i] = y

    # 각 쿼리마다 경로압축
    for i in range(N):
        find(i)

winner = set(P)
print(len(winner))

answer = set()
for i in range(N):
    answer.add(f"Kingdom of {cvt_rev[find(i)]}")

for ans in sorted(answer):
    print(ans)

 

코멘트

• .