💯Problem Solving
[BOJ] 2887 행성 터널
date
Aug 5, 2023
slug
boj-2887
author
status
Public
tags
Python
BOJ
summary
백준 2887번 문제풀이입니다.
type
Post
thumbnail
category
💯Problem Solving
updatedAt
Aug 22, 2023 04:39 PM
문제 링크
문제
때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.
행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.
민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.
문제풀이
x,y,z 각각을 기준으로 정렬후,
낮은 값부터 차례차례 비교해가며 graph 배열에 저장한다 이때
중복되는 값이 있을 수 있으므로 set으로 저장하고,
크루스칼 알고리즘을 사용하면 쉽게 풀린다.
import sys input = sys.stdin.readline N = int(input()) arr = [] for i in range(1, N+1): x,y,z = map(int, input().split()) arr.append((i,x,y,z)) # 행성 번호, x,y,z graphs = set() for k in range(1, 4): arr.sort(key = lambda x:x[k]) # x기준으로 정렬, y기준으로 정렬, z기준으로 정렬 for idx in range(len(arr)-1): p1, x1, y1, z1 = arr[idx] p2, x2, y2, z2 = arr[idx+1] value = min(abs(x1-x2), abs(y1-y2), abs(z1-z2)) graphs.add((p1, p2, value)) graphs = list(sorted(graphs, key=lambda x:x[2])) # value기준 오름차순 정렬 parents = [i for i in range(N+1)] # 자기자신을 부모로 가지는 배열 def find(node: int): if node == parents[node]: return node # 자기자신 parents[node] = find(parents[node]) return parents[node] def union(A:int, B:int): # A < B pa = find(A) pb = find(B) parents[pb] = pa # pb의 최상위 부모가 A의 최상위 부모가 됨 count = 0 weighted_value = 0 for item in graphs: if count == N - 1: break p1, p2, value = item if p1 > p2: # 작은거 정렬 p1, p2 = p2, p1 if find(p1) != find(p2): # 부모가 다르다 union(p1, p2) weighted_value += value count += 1 print(weighted_value)
파이썬 문제풀이 코드
시간복잡도
입력
첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다.
출력
첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.