[백준-파이썬] 21202: Conquest

문제 보러 가기!

TMI

내 기억 상 처음으로 푸는 영어 문제이다.

풀이 🦄

문제 이해를 돕기 위한 설명용 그림..ㅎㅎ

처음에 1번 섬에서 무조건 시작하고, 그 병력을 가지고 시작한다.
지배한 섬과 이어진 섬은 공격 후보가 된다.
이어진 섬의 병력이 우리(spanning nation) 병력보다 적을 때만!! 그 섬을 지배한다.

우선순위 큐를 활용하면 된다.
우선순위 큐, q에 공격할 수 있는 후보들(섬)을 집어 넣었다.

1. 인접 리스트로 섬들의 연결 관계를 저장한다.
2. 각 섬의 병력을 island_army 리스트에 저장한다.
3. 각 섬을 공격할 수 있는 후보(q)에 넣었는지 여부를 저장하는 visited 리스트를 만든다.
4. 1번 섬에서 시작한다. 우리 병력(spanning_army_cnt)를 1번 섬의 병력으로 업데이트하고, 1번 섬을 visited 체크 한다.
5. 1번 섬과 연결된 섬들을 q에 넣는다. 집어 넣을 때 그 섬의 병력과, 섬의 인덱스를 튜플로 넣었다! visited 체크도 한다.
6. 공격할 수 있는 섬이 더 이상 없을 때까지~~
   공격 당하는 섬의 병력을 우리 병력에 더한다.
   공격 당하는 섬과 연결된 섬 정보를 q에 넣고, 그 섬은 visited 체크를 한다.
7. 최종적으로 spanning_army_cnt를 출력하면 정답이다!

코드 👩‍💻

import sys, heapq

input = sys.stdin.readline

N, M = map(int, input().split())
connect = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    # 양방향
    connect[a].append(b)
    connect[b].append(a)

island_army = [0] + list(int(input()) for _ in range(N))
visited = [False] * (N + 1)

q = []
spanning_army_cnt = island_army[1]
visited[1] = True
for idx in connect[1]:
    q.append((island_army[idx], idx))
    visited[idx] = True

heapq.heapify(q)

while True:
    if not q or q[0][0] >= spanning_army_cnt:
        break

    while q and q[0][0] < spanning_army_cnt:
        cnt, idx = heapq.heappop(q)
        # 연결된 섬들을 대결 후보에 넣기
        for i in connect[idx]:
            if visited[i] == False:
                heapq.heappush(q, (island_army[i], i))
                visited[i] = True
        spanning_army_cnt += cnt
print(spanning_army_cnt)