[백준 - Python] 1045 - 도로

0.  문제 링크

 

 

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

1045번: 도로

---

1.  풀이 방법

 

 

1. edge가 (a, b)가 있다면, a < b가 되도록 모든 간선을 우선순위 큐에 넣음
   
   1. 이때 모든 간선의 개수가 m보다 작다면 -1을 출력
2. 크루스칼 알고리즘을 사용하여 mst를 만들었음
   1. 만약 mst가 만들어지지 않으면, 모두 연결되지 않는 것이므로 -1을 출력
3. 크루스칼 알고리즘을 진행하는 도중에 쓸모없는 간선은 따로 관리함
   1. 이때 우선순위 큐로 집어 넣음. 해당 간선들은 추후 m개의 개수를 맞추기 위해 사용될 예정임
4. 최종적으로 mst의 리스트와 쓸모 없는 간선의 리스트를 넣어서 m개의 리스트를 만듦
5. 해당 리스트에 있는 노드를 answer 리스트에 더함

---

2.  코드

 

 

import sys
import heapq
input = sys.stdin.readline


def my_par(x):
    while x != par[x]:
        x = par[x]
    return x


def union(x, y):
    par_x = my_par(x)
    while y != par[y]:
        temp, y = y, par[y]
        par[temp] = par_x
    par[y] = par_x


if __name__ == "__main__":
    n, m = map(int, input().split())
    maps = [list(input().strip()) for _ in range(n)]

    pq = []
    for i in range(n):
        for j in range(i, n):
            if maps[i][j] == 'Y':
                heapq.heappush(pq, (i, j))      # start < end가 될 수 있도록 엣지를 파악함

    if len(pq) < m:     # 엣지의 개수가 m이하라면 답이 없는 것
        print(-1)
        exit(0)

    trash = list()      # 우선 mst를 만들고, 뒤에 남는 애들을 넣어야 함
    par = [*range(n)]
    answer = [0] * n

    cnt = 0
    while pq:
        i, j = heapq.heappop(pq)
        if my_par(i) != my_par(j):
            union(i, j)
            answer[i] += 1      # 바로 정답에 더함
            answer[j] += 1
            cnt += 1
        else:
            heapq.heappush(trash, (i, j))       # 남는 쓰레기들을 넣어야 함

    if cnt != n - 1:        # 만약 mst가 만들어지지 않았으면 답이 없는 것임
        print(-1)
        exit(0)

    for _ in range(m - cnt):
        i, j = heapq.heappop(trash)
        answer[i] += 1
        answer[j] += 1

    print(*answer, sep=' ')

---

3.  마무리