백준 2887 행성터널 문제풀이

문제 

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

2887번: 행성 터널

 

 

문제 접근 방식

모든 행성이 터널 N-1개를 설치하여 최소 비용으로 서로 연결되어야하기 때문에 최소 스패닝 트리를 이용하여 문제를 풀려고 했다. 문제를 푸는 과정에서 막히는 부분이 있어서 해당 부분을 공유하려한다.

 

첫번째 사고 과정

노드마다 x,y,z 위치가 주어지고, 모든 행성을 최소 비용으로 연결해야 하기 때문에 모든 행성 p1, p2 사이의 최소 길이를 미리 구해놓고 최소 스패닝 트리를 쓰면 되지 않을까 생각 했다. 이렇게 풀려고 하면 O(N^2) 이 걸리며 N의 최댓값이 1e5 이기 때문에 시간 초과가 날 확률이 높다. 다른 방법을 찾아야한다.

 

두번째 사고 과정

문제를 어떻게 풀지 몰라서 예제 입력을 x,y,z축을 활용하여 3차원 공간에 그려보았다. 3차원 공간상에서 실질적인 거리와는 상관이 없어서 별 도움이 안되겠다 싶었는데, 3차원 좌표를 그릴 때 x,y,z 축을 그렸던게 문제를 푸는데 도움이 되었다. 행성의 x 거리, y거리, z 거리 중 최솟값을 비용으로 설정하면 되기에 각 행성의 x, y, z 축을 분리해도 될 것 같다는 생각이 들었다.

 

각 x, y, z축에 행성들을 위치 시키고, 이웃한 행성 간 거리를 구한다. 이때, 이웃하지 않은 행성 간 거리는 필요하지 않다(최소 거리로 행성들을 잇기 위해서는 이웃한 행성간 거리만 필요하다 > 그리디) . 각 축 상에서 이웃한 노드들의 비용을 구했다면, 이제 이것들을 한 곳에 모은 후 최소 비용인 간선을 탐색하여 최소 스패닝 트리를 만든다.

 

위와 같이 해도 되는 이유는 특정 노드 u, v 에 대해 특정 축(예를 들면 x 축)의 최소 비용의 간선을 우선적으로 찾게 될 것이고, 이후 다른 축(y,z 축) 의 거리를 선택했다고 할지라도 이미 스패닝 트리에 들어가 있기 때문에 pass를 하면 되기 때문이다. 이러한 방식을 통해 (x 축 상 거리, y축 상 거리, z 축 거리) 중 최솟값을 선택할 수 있게 된다. 

 

 

시간 복잡도

우선 순위 큐를 사용할 때 O(NlogN) 의 시간복잡도가 걸리며, 큐에 들어가는 요소의 크기는 x,y,z 축마다의 행성간 거리이기 때문에 3*(N-1)개의 요소가 들어가게 된다. N의 최댓값이 1e5이므로 시간 내에 동작하게 된다.

 

 

코드

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=int(input())
    planet_x=[]
    planet_y=[]
    planet_z=[]

    for i in range(n):
        x,y,z=map(int,input().split())

        # 축별로 (위치, 행성번호) 넣어줌
        planet_x.append((x,i))
        planet_y.append((y,i))
        planet_z.append((z,i))

    # 각 x,y,z 축별 오름차순 정렬
    planet_x.sort(key=lambda x:x[0])
    planet_y.sort(key=lambda x:x[0])
    planet_z.sort(key=lambda x:x[0])

    # x,y,z별로 행성 간 거리를 pq에 넣어줌
    pq=[]
    for i in range(1,n):
        # x 축 상에서 이웃한 행성간 거리를 구해서, pq 에 (거리, 행성1,행성2) 를 삽입
        distance=planet_x[i][0]-planet_x[i-1][0]
        u,v=planet_x[i-1][1],planet_x[i][1]
        heapq.heappush(pq,(distance,u,v))

        ## y, z 축도 위와 동일한 처리 진행
        heapq.heappush(pq, (planet_y[i][0]-planet_y[i-1][0], planet_y[i-1][1], planet_y[i][1]))
        heapq.heappush(pq, (planet_z[i][0]-planet_z[i-1][0], planet_z[i-1][1], planet_z[i][1]))


    ## pq 에는 ( 행성간 거리, 행성 1, 행성2) 요소들이 존재, 행성간 거리가 가장 짧은 것 부터 pop
    union_find=UnionFind(n)
    answer=0
    count=0
    while pq:
        if count == n-1:
            break

        w,p1,p2=heapq.heappop(pq)
        if union_find.find_parent(p1)==union_find.find_parent(p2):
            continue

        union_find.union(p1,p2)
        answer+=w
        count+=1

    print(answer)

 

 

회고

노드 간 비용에 대한 처리를 어떻게 해야할지 정말 막막했던 것 같다. 문제에서 두 노드간 비용이 3차원상에서의 거리가 아닌 x, y, z 사이의 거리 중 최솟값이라는 특수한 조건 때문에 각 축을 개별적으로 생각해도 된다. 이게 핵심 아이디어였다. 각 축에 대해 쪼갠 후에 합쳐서 생각할 수도 있구나를 경험할 수 있었다.