[2022 하계 모각코] 팀 "한 명 어디갔노" 6회차 - 계획 및 결과

목표
알고리즘 실력 향상을 위해 백준에서 출제하는 문제들을 풀어본다.

사용 언어
Python

일정
6회차: 8/4 14:00 ~ 17:00
목표 : 백준 그래프 이론 1 ~ 2문제 풀기

1. 백준 2887번

풀이

• 크루스칼 알고리즘을 이용하는데 간선에 대한 정보가 없으므로 필요한 간선정보를 만들어야 한다.
• x, y, z 좌표를 따로 입력받아 정렬한다.
• 행성의 번호와 비용차이를 같이 입력받아 리스트에 저장하고 정렬한다.
• 최소신장 트리를 만들 때까지 union을 한 후 최소비용을 구한다.

Code

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, 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())
parent = [i for i in range(n + 1)]

x_list = []
y_list = []
z_list = []

for i in range(1, n + 1):
    x, y, z = map(int, input().split())
    x_list.append((x, i))
    y_list.append((y, i))
    z_list.append((z, i))

x_list.sort()
y_list.sort()
z_list.sort()

calc_list = []

for i in range(1, n):
    calc_list.append((abs(x_list[i][0] - x_list[i-1][0]), x_list[i][1], x_list[i-1][1]))
    calc_list.append((abs(y_list[i][0] - y_list[i-1][0]), y_list[i][1], y_list[i-1][1]))
    calc_list.append((abs(z_list[i][0] - z_list[i-1][0]), z_list[i][1], z_list[i-1][1]))

calc_list.sort()

count = 0
answer = 0

for temp in calc_list:
    cost, a, b = temp
    if find_parent(parent, a) != find_parent(parent, b):
        union(parent, a, b)
        answer += cost
        count += 1
    if count == n:
        break

print(answer)

결과