[BOJ/백준] 1045 도로

import sys
import heapq
def input():
    return sys.stdin.readline().rstrip()
 
 
 
def find_parents(X):
    if X == make_set[X]:
        return X
    make_set[X] = find_parents(make_set[X])
    return make_set[X]
 
 
def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)
 
    if X !=Y:
        if ranks[X]< ranks[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if ranks[X] == ranks[Y]:
            ranks[X] += 1
        return True
    return False
N,M = map(int,input().split())
 
edge_list = []
 
for x in range(N):
    temp = list(input())
    for y in range(x+1,N):
        if temp[y] == 'Y':
            heapq.heappush(edge_list,(x,y))
city_cnt = 0
if len(edge_list) >= M:
    result = [0 for _ in range(N)]
    make_set = [i for i in range(N)]
    ranks = [1 for _ in range(N)]
    remain_list = []
    while edge_list:
        node_a,node_b = heapq.heappop(edge_list)
        if union(node_a,node_b):
            city_cnt += 1
            result[node_b] += 1
            result[node_a] += 1
        else:
            heapq.heappush(remain_list,(node_a,node_b))
    if city_cnt != N-1:
        print(-1)
    else:
        remain_cnt = M - city_cnt
 
        while remain_cnt>0:
            node_a,node_b = heapq.heappop(remain_list)
            result[node_a] += 1
            result[node_b] += 1
            remain_cnt -= 1
        print(*result)
else:
    print(-1)

이 문제는 문제를 이해하는데 힘들었고, 구현을 하는데 어려운 점이 많았었다.

 

평소에 MST 관련 문제는 프림 알고리즘을 주로 이용해서 풀었지만, 이 문제를 푸는데에는 크루스칼 알고리즘을 이용했다.

 

문제를 푸는 방식은 다음과 같다. 모든 간선들을 저장을 해주는데, 그 조건은 x,y 에서 y는 무조건 x보다 큰 경우의 간선만 저장을 시켜준다.

 

그래서 모든 간선을 저장시켰는데 주어진 M보다 적을때에는 -1을 출력을 해준다.

 

그리고 크루스칼 알고리즘을 이용해서 풀면된다.

 

그러나, 여기서 다른 점은 우리가 이미 union이 된 간선들을 버리게 되는데, 이걸 따로 저장을 시켜놓는다.

 

그리고 우리는 모든 크루스칼 알고리즘을 돌린뒤에, 모든 도시가 연결이 안되어있으면 -1을 출력을 해주고,

 

그리고 우리는 무조건 도로 M개를 무조건 연결을 해야하므로, 우리는 크루스칼 알고리즘을 통해 N-1개를 연결을 해놓은 상태이다.

 

그러므로 M-(N-1)개의 도로를 추가적으로 연결을 시켜주면 된다.

 

그래서 우리는 저장시켜놓은 도로들을 우선순위가 높은 것부터 뽑아서 연결을 시켜주면 된다.

 

 

import sys
from collections import deque
def input():
    return sys.stdin.readline().rstrip()
 
 
 
def find_parents(X):
    if X == make_set[X]:
        return X
    make_set[X] = find_parents(make_set[X])
    return make_set[X]
 
 
def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)
 
    if X !=Y:
        if ranks[X]< ranks[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if ranks[X] == ranks[Y]:
            ranks[X] += 1
        return True
    return False
N,M = map(int,input().split())
 
edge_list = deque()
result = [0 for _ in range(N)]
make_set = [i for i in range(N)]
ranks = [1 for _ in range(N)]
 
city_cnt = 0
for x in range(N):
    temp = list(input())
    for y in range(x+1,N):
        if temp[y] == 'Y':
            if union(x,y):
                city_cnt += 1
                result[x] += 1
                result[y] += 1
            else:
                edge_list.append((x,y))
 
 
if city_cnt<N-1 or city_cnt+len(edge_list)<M:
    print(-1)
else:
    remain_cnt = M - city_cnt
 
    while remain_cnt>0:
        x,y = edge_list.popleft()
        result[x] += 1
        result[y] += 1
        remain_cnt -= 1
    print(*result)

이건 코드를 좀 더 개선시킨 버전이다.

 

달라진것은 heapq 대신 그냥 앞에서부터 차근차근 해주는 방식으로 바꿔준 것이다.

 

이 문제는 크루스칼을 이용하는 것뿐만 아니라, 문제를 잘 분석해야 풀 수 있었떤 문제였다.