백준 1647 도시 분할 계획 문제풀이

문제 

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

 

 

 

문제 접근 방식

두 집 사이에 항상 길이 필요하며 그 비용을 최소화 해야하기 때문에 최소 스패닝 트리를 활용해서 문제를 풀려고 했다. 이때 어떻게 최소 스패닝 트리를 활용해야하나 고민을 했는데 사고의 흐름을 정리하려한다.

 

1. 첫번째 사고

처음에는 최소 스패닝 트리를 구한 후 그 중 최대 간선의 길이를 찾아서 제거하면 되지 않을까 생각을 했다. 

하지만, 최소 스패닝 트리가 아닌 일반 스패닝 중 간선 하나를 제거해서 답안이 나오는 경우도 있을 수도 있다고 판단했다. 즉, 최소 스패닝 트리에서 간선을 제거하는 것이 정답을 보장할 수 없다고 판단하여서 다른 방법을 찾아봤다.

결과적으로는, 이렇게 풀어도 정답이 나오지만 다른 스패닝 트리에서 정답이 나오는 경우의 변수를 제거하지는 못하는 것 같다.

 

2. 두번째 사고

어떻게 풀어야할지 몰라 직접 입력 예시를 활용했다. 입력 예시를 크루스칼 알고리즘을 활용해서 간선을 하나씩 이어보다가 크루스칼 알고리즘이 계속해서 최소 간선을 선택하는 그리디라는 것과 간선을 하나 덜 선택하면 그룹이 두 개로 된다는 점을 알게 되어 이를 활용했다.

 

기존 크루스칼 알고리즘이 노드 개수 V보다 하나 더 적은 수의 간선을 이었다면, 여기서 (V-2) 개까지의 간선을 선택하여 완전한 최소 스패닝 트리가 되기 전까지만 노드를 이어준다.

 

 

시간 복잡도

유니온 파인드의 find, union 이 상수시간이 걸리고, 우선순위 큐의 시간복잡도가 O(ElogE)이므로 전체 시간복잡도는 O(ElogE)이다. E의 최댓값이 1e6이므로 시간내에 동작함을 알 수 있다.

 

 

코드

import sys
import heapq

input=sys.stdin.readline
class UnionFind:
    def __init__(self,n):
        self.parents=[i for i in range(n+1)]
        self.heights=[0 for _ in range(n+1)]

    def find_parent(self,node):
        if self.parents[node]==node:
            return node
        self.parents[node]=self.find_parent(self.parents[node])
        return self.parents[node]

    def union(self,u,v):
        u=self.find_parent(u)
        v=self.find_parent(v)
        if u==v:
            return

        if self.heights[u]<self.heights[v]:
            u,v=v,u

        self.parents[v]=u

        if self.heights[u]==self.heights[v]:
            self.heights[u]+=1

if __name__=='__main__':
    n,m=map(int,input().split())
    pq=[]

    for _ in range(m):
        a,b,c=map(int,input().split())

        heapq.heappush(pq,(c,a,b))

    union_find=UnionFind(n)
    count=0
    answer=0
    while pq:
        if count == n - 2:
            break
        c,a,b=heapq.heappop(pq)
        if union_find.find_parent(a)==union_find.find_parent(b):
            continue

        union_find.union(a,b)
        answer+=c
        count+=1

    print(answer)

 

 

회고

처음 답안을 제출할 때 틀렸습니다가 떴는데, 처음에는 v-2개의 간선을 선택하는 풀이 방향이 잘못된건가를 생각했다. 하지만 대부분의 경우에서 동작을 하는 로직이었기 때문에 특수한 상황에서 에러가 발생한다고 생각했다. 주어진 상황에서 N=2 이고 간선이 주어질 때가 가장 특수한 상황이었기에 해당 부분에서 오류가 발생하는 부분을 수정하였다. 

 

첫번째 코드

import sys
import heapq

input=sys.stdin.readline
class UnionFind:
    def __init__(self,n):
        self.parents=[i for i in range(n+1)]
        self.heights=[0 for _ in range(n+1)]

    def find_parent(self,node):
        if self.parents[node]==node:
            return node
        self.parents[node]=self.find_parent(self.parents[node])
        return self.parents[node]

    def union(self,u,v):
        u=self.find_parent(u)
        v=self.find_parent(v)
        if u==v:
            return

        if self.heights[u]<self.heights[v]:
            u,v=v,u

        self.parents[v]=u

        if self.heights[u]==self.heights[v]:
            self.heights[u]+=1

if __name__=='__main__':
    n,m=map(int,input().split())
    pq=[]

    for _ in range(m):
        a,b,c=map(int,input().split())

        heapq.heappush(pq,(c,a,b))

    union_find=UnionFind(n)
    count=0
    answer=0
    while pq:
        c,a,b=heapq.heappop(pq)
        if union_find.find_parent(a)==union_find.find_parent(b):
            continue

        union_find.union(a,b)
        answer+=c
        count+=1
        
        if count == n - 2:
            break

    print(answer)

 

 

추가

이번 문제에서는 2개의 그룹으로 분할하여 v-2개를 선택했지만, 추후에 변형으로 3개, 4개로 그룹을 쪼개는 방식을 구할 때도  크루스칼을 활용하여 v-3, v-4,...개의 간선을 선택하여 문제를 풀면 될 것 같다.