[백준 / 15809] 전국시대 - Python

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

15809번: 전국시대

 

<풀이>

Union-Find 알고리즘을 응용하여 풀 수 있는 문제다.

 

conturies에 각 국의 전투력 또는 점령국(속국의 경우)을 적어놓은다.

 

전투력과 헷갈릴 수 있으므로, 속국인 경우에 점령국의 Index를 -1 을 곱한 음수 값으로 저장한다.

 

따라서 점령국의 경우 전투력이 나오고, 속국인 경우에는 해당 점령국의 인덱스가 저장되는 것이다.

 

따라서, 전투를 하거나 동맹을 맺는 경우 속국으로 계산 하는 것이 아닌 점령국을 대상으로 계산을 진행하면 된다.

 

 

<전체 코드>

 

import sys

N, M = map(int, sys.stdin.readline().split())
conturies = [0]
for _ in range(N):
    conturies.append(int(sys.stdin.readline()))


def find(n):
    now = conturies[n]
    if now < 0:
        return find(-1*now)
    else:
        return n

for _ in range(M):
    com, x, y = map(int, sys.stdin.readline().split())
    find_x = find(x)
    find_y = find(y)

    if com == 1:
        conturies[find_x] += conturies[find_y]
        conturies[find_y] = -1*find_x

    else:
        if conturies[find_x] == conturies[find_y]:
            conturies[find_x] = 0
            conturies[find_y] = 0
        elif conturies[find_x] > conturies[find_y]:
            conturies[find_x] -= conturies[find_y]
            conturies[find_y] = -1*find_x
        else:
            conturies[find_y] -= conturies[find_x]
            conturies[find_x] = -1*find_y

answer = []
for i in conturies:
    if i > 0:
        answer.append(i)
answer.sort()
print(len(answer))
print(*answer)