[알고리즘] 행성 터널 python(boj 2887)

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

 

 

문제

때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.

행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.

민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다. 

출력

첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.

 

 

0. 3차원 공간에서 차원 축소를 통한 효율적 거리 계산

이 문제에서 각 행성은 (x,y,z)(x,y,z) 좌표를 가진 3차원 공간에 위치합니다. 모든 행성을 서로 연결하는 터널의 비용을 최소화하는 것이 목표인데, 각 좌표 간 최소 거리만을 계산하므로, 단순히 3차원 거리로 계산하면 비효율적일 수 있습니다. 최대 100,000개의 행성이 주어지기 때문에, 모든 행성 쌍에 대한 거리를 계산하기엔 매우 비효율적입니다. 따라서, 각 좌표축에 대해 행성을 정렬하는 방식으로 계산을 단순화할 수 있습니다.

차원 축소가 작동하는 이유

두 행성 A(xA,yA,zA)A(xA,yA,zA)와 B(xB,yB,zB)B(xB,yB,zB) 사이의 터널 비용은 min⁡(∣xA−xB∣,∣yA−yB∣,∣zA−zB∣)min(∣xA−xB∣,∣yA−yB∣,∣zA−zB∣)로 정의됩니다. 여기서 우리는 각 좌표 xx, yy, zz별로 행성을 정렬한 후, 인접한 행성 간의 거리만 고려합니다. 각 축에 대해 인접한 행성은 해당 축에서 최소 거리를 가질 가능성이 높기 때문에, 각 좌표 정렬 후 인접 행성 간 거리만 계산해도 충분한 정보를 얻을 수 있습니다. 이는 전체 행성 연결에 필요한 최소한의 거리 정보만 고려하게 해줍니다.

1. 각 좌표별 정렬:
   행성을 xx, yy, zz 좌표별로 각각 정렬하여 세 개의 리스트를 만듭니다. 각 리스트에서 인접한 행성들만 연결하면 되므로, 불필요한 연결을 최소화할 수 있습니다.
2. 최소 거리 계산:
   정렬된 리스트에서 인접 행성 간의 최소 거리를 계산합니다. 이렇게 얻은 제한된 연결 정보만으로도 모든 행성을 연결하는 데 충분한 에지가 확보됩니다.

 

크루스컬 알고리즘

1. 행성 정보 입력 및 준비

먼저, 행성의 개수 NN을 입력받고, 각 행성의 좌표를 (x,y,z)(x,y,z)로 입력받아 planets 리스트에 저장합니다. 각 행성은 3차원 공간에서 하나의 점으로 취급되며, 좌표는 planets 리스트에 (index,x,y,z)(index,x,y,z) 형태로 저장됩니다.

2. 차원별 정렬을 통한 인접 행성 간 거리 계산

다음으로, 각 좌표축별로 행성들을 정렬하여 거리 계산의 효율성을 높입니다. ps 리스트에는 xx, yy, zz 좌표에 대해 정렬된 planets 리스트가 저장됩니다.

이렇게 하는 이유는 각 축에서 인접한 행성들 간의 거리만 계산하여 터널 연결 비용을 구할 수 있기 때문입니다. 따라서 불필요한 거리 계산을 줄이고, 최적의 연결을 얻을 수 있습니다.

3. addBoard 함수: 인접 행성 간 거리 계산 및 간선 목록 추가

addBoard 함수는 주어진 정렬 리스트 pp를 기반으로 인접한 행성 간의 거리를 계산하고, 간선을 q에 추가합니다. dist 함수는 두 행성 간의 각 축의 거리를 계산하고 그중 최소값을 반환하여 비용으로 사용합니다.

• 리스트 pp의 인접한 행성 쌍 간의 거리만 계산하여, 해당하는 간선을 q 리스트에 추가합니다.
• xx, yy, zz 축 각각에 대해 addBoard를 호출해, 각 축에서 인접한 행성 간 거리 정보가 q에 추가되도록 합니다.

이렇게 하면 모든 가능한 연결을 고려하는 대신, 인접한 연결만을 간선으로 추가하여 효율성을 높일 수 있습니다.

4. 중복 간선 제거 및 간선 정렬

각 좌표축에서 얻은 인접 간선 정보들이 중복될 수 있으므로 q 리스트의 중복 간선을 제거하고, 비용 순으로 정렬합니다. 이렇게 정렬된 간선 리스트는 크루스칼 알고리즘의 다음 단계에서 사용됩니다.

5. 유니온-파인드 (Union-Find) 자료 구조 준비

크루스칼 알고리즘은 최소 비용의 신장 트리를 구하는 알고리즘으로, 사이클을 방지하기 위해 유니온-파인드 자료 구조를 사용합니다.

• find 함수는 특정 노드의 최상위 부모를 찾고, 경로 압축을 통해 효율성을 높입니다.
• union 함수는 두 집합을 하나로 합칩니다. 만약 두 행성이 서로 다른 집합에 속해 있다면, 두 집합을 하나로 합칩니다.

6. 최소 신장 트리 (MST) 구축

for 문을 사용해, 정렬된 간선 리스트 q에서 가장 비용이 적은 간선부터 차례로 확인합니다. 각 간선을 확인하며 다음 과정을 수행합니다:

• 현재 간선이 연결하는 두 행성이 서로 다른 집합에 속해 있다면, union 함수를 사용해 두 집합을 하나로 합치고, 해당 간선의 비용을 res에 더합니다.
• flagCount는 연결해야 할 남은 간선의 수를 추적하는 변수로, 이를 줄여나가다가 N−1N−1개의 간선이 연결되면 루프를 종료합니다. 이는 모든 행성이 연결되었음을 의미합니다.

7. 결과 출력

모든 행성을 연결하는 데 필요한 최소 비용이 res에 저장되며, 이를 출력합니다.

요약

1. 행성 정보를 입력받고, 각 축에 대해 정렬하여 인접 행성 간 거리만 계산해 q에 간선 정보로 추가합니다.
2. 중복 간선을 제거하고 비용 순으로 정렬합니다.
3. 크루스칼 알고리즘을 사용해, 유니온-파인드로 사이클을 방지하면서 최소 비용 신장 트리를 구축합니다.
4. 모든 행성이 연결될 때까지 간선을 추가하며 최소 비용을 계산하고, 최종 비용을 출력합니다.

이 코드는 차원 축소와 크루스칼 알고리즘을 결합하여, 많은 수의 행성 간 효율적으로 최소 비용을 구하는 문제를 해결합니다.

 

import sys
input = sys.stdin.readline

N = int(input())
planets = []
for ind in range(N):
    x, y, z = list(map(int, input().split()))
    planets.append((ind, x, y, z))

board = [[] for _ in range(N) ]

ps = list(map(lambda ind: sorted(planets, key= lambda x: x[ind]), range(1, 4)))
q = []
def dist(x, y) :
    currentDist = list(map(lambda ind: abs(x[ind] - y[ind]), range(1, 4)))
    return min(currentDist)

def addBoard(p) :
    for ind in range(len(p)) :
        (pInd, _, _, _) = p[ind]
        if ind > 0 :
            prevInd = p[ind - 1][0]
            curDist = dist(planets[pInd], planets[prevInd])
            nexts = prevInd, pInd if prevInd < pInd else prevInd, pInd
            q.append((curDist, nexts[0], nexts[1]))
        if ind < N - 1 :
            nextInd = p[ind + 1][0]
            curDist = dist(planets[pInd], planets[nextInd])
            nexts = nextInd, pInd if nextInd < pInd else nextInd, pInd
            q.append((curDist, nexts[0], nexts[1]))

[addBoard(x) for x in ps]

parents = list(range(N))

def find(x) :
    if parents[x] != x :
        parents[x] = find(parents[x])
    return parents[x]

def union(x, y) :
    xP, yP = find(x) , find(y)
    if xP < yP :
        parents[y] = xP
        parents[yP] = xP
    elif yP < xP :
        parents[x] = yP
        parents[xP] = yP
q = list(set(q))
q.sort()
flagCount = N - 1
res = 0

for w, s, e in q :
    if find(s) != find(e) :
        union(s, e)
        flagCount -= 1
        res += w
        if flagCount == 0 :
            break
print(res)

 

 

프림 알고리즘

 

프림 알고리즘을 사용한 이 코드의 진행 과정을 단계별로 설명하겠습니다. 프림 알고리즘은 주어진 그래프에서 최소 비용으로 모든 노드를 연결하는 최소 신장 트리(MST)를 만드는 방법 중 하나로, 임의의 시작점에서 시작하여 점차적으로 MST를 확장해 나가는 방식입니다. 코드의 흐름을 보면서 각 단계를 설명하겠습니다.

코드 설명 및 흐름

1. 입력 처리와 초기화:
   • N은 행성의 개수이며, planets 리스트에는 각 행성의 인덱스와 3차원 좌표 (x, y, z)가 저장됩니다.
2. 행성 연결을 위한 간선 구성 (그래프 생성):
   • ps는 좌표의 각 축 (x, y, z)별로 정렬된 행성 리스트입니다. 각각의 축에 대해 인접한 두 행성을 연결하는 간선을 생성합니다.
   • makeRoutes 함수는 각 좌표별 정렬된 행성 리스트를 받아서 인접한 행성 간의 거리를 계산하고, 이를 기반으로 간선을 구성해 graph 딕셔너리에 추가합니다.
   • 거리는 dist 함수에서 최소 비용으로 정의되며, min(|xA - xB|, |yA - yB|, |zA - zB|)로 계산됩니다.
3. 프림 알고리즘을 통한 MST 생성:
   • 시작 노드: 프림 알고리즘은 임의의 시작점에서 시작하여 노드를 하나씩 추가하면서 최소 신장 트리를 확장합니다. 여기서는 (0, 0)으로 시작하며, 이는 가중치가 0이고 노드가 0인 튜플을 의미합니다.
   • 우선순위 큐 활용: task는 우선순위 큐(heapq)로, 현재 트리에 가장 적은 비용으로 연결 가능한 노드를 선택하는 역할을 합니다.
   • 방문 체크와 비용 갱신: visited 리스트는 방문한 노드를 추적합니다. 이미 방문한 노드는 건너뛰어 순환을 방지합니다.
   • 트리 확장:
     • 최소 비용 간선을 선택하고 방문하지 않은 노드에 대해 방문을 표시합니다.
     • 선택한 노드의 비용을 res에 누적하고 flagCount를 감소시킵니다.
     • 이 과정을 모든 노드가 연결될 때까지 반복합니다. (즉, flagCount가 0이 될 때까지)
4. 결과 출력:
   • 모든 노드를 연결하는 최소 신장 트리의 총 비용을 res에 출력합니다.

주요 로직 요약

프림 알고리즘의 핵심은, 이미 선택된 노드 집합에 새로운 노드를 최소 비용으로 연결하는 간선을 하나씩 추가하여 신장 트리를 확장하는 방식입니다. 이를 위해 우선순위 큐를 사용해 비용이 가장 작은 간선을 선택하며, 방문한 노드는 재방문하지 않도록 관리합니다.

 

 

import sys
import collections
import heapq
input = sys.stdin.readline

N = int(input())
planets = []
for ind in range(N):
    x, y, z = list(map(int, input().split()))
    planets.append((ind, x, y, z))

board = [[] for _ in range(N) ]
ps = list(map(lambda ind: sorted(planets, key= lambda x: x[ind]), range(1, 4)))
# (가중치, 시작점, 끝점)
graph = collections.defaultdict(list)

def dist(x, y) :
    return min(map(lambda ind : abs(x[ind] - y[ind]), range(1, 4)))
 
def makeRoutes(sortedP) :
    for ind in range(N - 1) :
        cost = dist(sortedP[ind], sortedP[ind + 1])
        graph[sortedP[ind + 1][0]].append((cost, sortedP[ind][0]))
        graph[sortedP[ind][0]].append((cost, sortedP[ind + 1][0]))

[makeRoutes(x) for x in ps]

task = [(0, 0)]
visited = list(map(lambda _: False, range(N)))
res = 0
flagCount = N
while task :
    w, v = heapq.heappop(task)
    if visited[v] :
        continue
    visited[v] = True
    res += w
    flagCount -= 1
    if flagCount == 0 :
        break
    for nextW, nextV in graph[v] :
        if visited[nextV] == False:
            heapq.heappush(task, (nextW, nextV))
print(res)