백준 1045번 도로

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

 

 

문제와 입출력 조건은 다음과 같다.

 

 

 

 

 

우선순위에 따라 정렬해야 되기에 우선순위 큐나 정렬된 리스트를 생각해볼 수 있었다.

인접행렬로 탐색하면서 저장하고 둘 중 하나로 정리를 하면 될 것 같은데 더 이상의 아이디어가 생각나지 않았다.

 

몇 번 도전했지만 계속 틀려서 다른 분의 풀이를 보면서 이 문제를 풀 때 주의해야 할 점을 정리했다.

 

 

• MST 구성 시 반드시 N-1개의 간선을 사용해야 한다.
• 도로의 우선순위를 정확히 반영하여 내림차순으로 처리해야 한다.
• Union-Find를 사용해 두 도시가 연결되었는지 확인한다.
• 남는 도로는 나중에 필요하면 추가로 사용한다.
• MST가 유효하지 않다면 -1을 출력해야 한다.
• 출력 형식에 맞게 도로 개수를 각 도시별로 출력해야 한다

 

 

 

 

이에 맞게 짜진 코드는 밑에 코드와 같고 해석을 해보았다.

 

 

 

- n, m을 입력받아 각각 도시의 개수와 도로의 수를 저장하고 maps는 인접 행렬을 리스트 형태로 저장한다.

- pq를 생성하여 도시 간의 연결 정보를 저장한다.

- 인접 행렬을 순회하면서 두 도시 i와 j가 연결되어 있는 경우 (i, j) 튜플을 힙에 추가한다.

- 만약 pq의 길이가 m보다 작으면 도로의 개수가 부족하므로 -1을 출력하고 프로그램을 종료한다.

- trash 리스트를 생성하여 MST에 포함되지 않는 도로를 저장한다.

- par 배열을 초기화하여 각 도시가 자기 자신을 부모로 가지도록 설정한다.

- answer 배열을 초기화하여 각 도시의 도로 개수를 카운트한다

Union-Find (서로소 집합) 구현

• my_par(x) 함수: 주어진 노드 x의 부모 노드를 찾는 경로 압축(path compression) 방식의 함수다.
• union(x, y) 함수: 두 도시 x와 y를 연결합니다. 각 도시의 부모를 찾아 두 도시를 같은 집합으로 합친다.

-힙에서 도로를 하나씩 꺼내면서, 두 도시가 이미 연결되어 있지 않으면 union을 수행하여 두 도시를 연결하고 answer 배열을 업데이트한다. 연결된 도시의 도로 개수를 세고 cnt를 증가시킨다.

- 이미 연결되어 있는 도시의 도로는 trash 리스트에 저장한다.

- 만약 cnt가 n - 1이 아니면 모든 도시를 연결할 수 없다는 뜻이므로 -1을 출력하고 종료한다.

- MST가 완성된 후 남은 도로를 trash에서 꺼내어 answer에 추가하여 각 도시의 도로 개수를 증가시킨다.

- 최종적으로 각 도시의 도로 개수를 공백으로 구분하여 출력한다.

 

 

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=' ')