새소식

반응형
Algotithms

[백준] 2887 행성 터널 🌟

  • -
728x90
반응형

문제

  • N개의 행성에 N-1개의 터널을 만들어 서로 연결되게 할 때, 필요한 최소 비용은?
    • 1 <= N <= 100,000
  • 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)

 

풀이

  • $O(N^2)$ 이 아닌 풀이가 생각나지 않아 한참 고민한 문제.
  • 크루스칼로 $O(NlogN)$ 안에 해결 가능하다.
  • 포인트는 x, y, z 축으로 각각 정렬한 후 N-1 개의 간선만 고려해서 최소 신장 트리를 만든다는 것
    • 정렬하고 난 뒤 바로 옆 간선이 아니면 더 큰 비용이 되니까.. 
  • sys.stdin.readline 사용해야 시간초과 안걸린다.

 

import sys
input = sys.stdin.readline

# 부모 찾기
def find_parent(parent, x):
    if parent[x] != x :
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b


# 입력 받기
N = int(input())

x = []  # x 좌표
y = []  # y 좌표
z = []  # z 좌표
for i in range(1, N+1):
    coor = list(map(int, input().split()))
    x.append((coor[0], i))
    y.append((coor[1], i))
    z.append((coor[2], i))

x.sort()
y.sort()
z.sort()

parent = [i for i in range(N+1)]    # 부모 테이블
edges = []       # 간선 리스트
answer = 0       # 터널 연결 비용

# 각 좌표별 N-1 개의 간선 추가
for i in range(N-1):
    edges.append((x[i+1][0] - x[i][0], x[i+1][1], x[i][1]))
    edges.append((y[i+1][0] - y[i][0], y[i+1][1], y[i][1]))
    edges.append((z[i+1][0] - z[i][0], z[i+1][1], z[i][1]))

edges.sort()

for edge in edges:
    cost, a, b = edge
    # 행성 터널이 없는 경우에만 연결
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        answer += cost

print(answer)

 

 

References

  • 이것이 코딩테스트다 Q 44
  • 백준 2887번
반응형
Contents

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.