[BOJ][Python] 백준 1045 번: 도로

1일 1PS 71일차!

📚 문제

---

골드 1 도로

💡 풀이 과정

---

• 최소 스패닝 트리 를 그대로 사용하였다.

• 문제 해석에 조금 어려움이 있었다.
• 도로 연결 시 연결되는 도로의 합이 가장 적은 것의 우선순위가 높다.
• (0, 4) 와 (1, 3) 을 연결 시에는 서로 가장 작은 정수를 비교해 (0 < 1) 이므로 (0, 4) 의 우선순위가 더 높다.
• 3 번 도시와 연결될 때, (0, 1, 4) 번 도시 그룹, (2, 3, 5) 도시 그룹에서는 역시 가장 작은 정수를 비교해 (0, 1, 4) 번 도시 그룹과 연결하는 것이 우선순위가 더 높다.
  • 이때 연결되는 도로를 모두 살펴보면 (3, 0) (3, 1) … 중에서 결국 (3, 0) 의 우선 순위가 가장 높으므로 추가로 신경쓰지 않아도 된다.
• 그렇다면 결국 우선순위가 높은 도로부터 탐색하면서 MST(최소 스패닝 트리) 를 생성하고 남은 M 횟수만큼 우선순위대로 도로를 추가하기만 하면 된다.
• 2중 for 문으로 도로가 존재하는 곳을 탐색한다.
• 도로를 추가할 수 있다면 추가하고 사이클이 만들어진다면 해당 도로를 queue 에 저장한다.
• 끝까지 탐색 후 MST 가 생성되었는 지 판단한다.
  • MST 가 없다면 -1 을 출력한다.
  • MST 가 생성되었다면 queue 에 존재하는 도로를 우선순위에 따라 추가한다.
    • 모두 추가했을 때 M 개의 도로가 채워지지 않는다면 -1 을 출력한다.
• 도로를 추가 시 양 끝 도시를 카운팅한다.

📌포인트

---

• MST 가 생성되지 않았을 경우를 따로 고려해줘야한다.

💻 코드

---

import sys
from collections import deque

class UnionFind():
    def __init__(self, N):
        self.data = [i for i in range(N + 1)]

    def find(self, N):
        if N == self.data[N]:
            return N
        self.data[N] = self.find(self.data[N])
        return self.data[N]

    def union(self, N, M):
        self.data[self.find(M)] = self.find(N)


input = sys.stdin.readline

N, M = map(int, input().split())
roads = [list(input()) for _ in range(N)]
uf = UnionFind(N)
count = [0] * N
cnt = 0
queue = deque()

# 최소 스패닝 트리
for i in range(N):
    for j in range(i + 1, N):
        # 도로가 존재하지 않으면 pass
        if roads[i][j] == "N":
            continue
        # 같은 집합이면 pass
        if uf.find(i) == uf.find(j):
            queue.append((i, j))
            continue

        # union 후 양 끝 도시 추가
        uf.union(i, j)
        count[i] += 1
        count[j] += 1
        cnt += 1

# MST 가 만들어지지 않았을 경우
if cnt < N - 1:
    print(-1)

# MST 가 만들어졌을 경우
else:
    # 남아있는 도로를 M 에 맞춰 추가
    while queue and cnt < M:
        i, j = queue.popleft()
        count[i] += 1
        count[j] += 1
        cnt += 1

    # 모든 도로를 추가했는데 M 이 채워지지 않았을 경우
    if cnt < M:
        print(-1)
    # M 에 맞게 도로가 추가된 경우
    else:
        print(*count, sep=" ")