[백준(BOJ)] 2887번 : 행성 터널 - PYTHON[파이썬]

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

2887번: 행성 터널

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 정렬
• 최소 스패닝 트리

 

---

 

⊙ 문제 접근 과정

 

먼저 사용자에게 입력받은 3차원 행성 좌표를 저장한다.

그리고 그 값들을 토대로 행성 사이의 거리를 각각 구해주고 크루스칼 알고리즘을 사용한다.

 

크루스칼 알고리즘을 사용하면 최소 스패닝 트리를 구할 수 있다.

 

최소 스패닝 트리란 신장 트리 중에서도 최소한의 비용으로 만들 수 있는 최소 신장 트리를 찾는 알고리즘이다. 그러니 행성 간 가장 짧은 거리를 구할 수 있다!!!

 

아래에 정리된 코드를 통해 크루스칼 알고리즘을 어떻게 사용하여 최소 스패닝 트리를 구하였는지 확인해보자!

---

 

⊙ 문제 풀이

 

import sys

input = sys.stdin.readline

N=int(input())
parent=[i for i in range(N)]
tempEdges = []
edges = []
result = 0

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

def union(parent,a,b):
    rootA = find(parent,a)
    rootB = find(parent,b)

    if rootA<rootB: parent[rootB]=rootA
    else: parent[rootA]=rootB

for i in range(N):
    a, b, c = map(int, input().split())
    tempEdges.append((a,b,c,i))

for i in range(3):
    tempEdges.sort(key=lambda x:x[i])
    for j in range(1, N):
        edges.append((abs(tempEdges[j-1][i]-tempEdges[j][i]),tempEdges[j-1][3],tempEdges[j][3]))

edges.sort()

for i in range(len(edges)):
    if find(parent, edges[i][1]) != find(parent, edges[i][2]):
        union(parent,edges[i][1],edges[i][2])
        result+=edges[i][0]

print(result)

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!