[백준 2887번 / python] 행성 터널 - 실패

2887번: 행성 터널

멋모르고 도전했던 행성 터널문제..

테스트 케이스는 통과가 되는데, 제출 결과는 '틀렸습니다'..😂
백준 문제를 오랜만에 풀어봤는데..
개인적으로는 프로그래머스가 해당 문제에 대해 서로 공유할 수 있는 커뮤니티 형성이 더 잘 되어 있어서
문제가 막힐 때 힌트를 얻어가기 더 쉬워서 좋다.

물론 물어볼 곳이 따로 있다면 상관없지만, 혼자 공부하는 사람들에게는 가끔 벅차😅ㅠㅠ

 

로직

0. 문제에서 주어진 input으로 예시를 들어보겠다

5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

1. 먼저 x, y, z에 대해서 각각 (value, index)를 원소로 한 minHeap을 만든다.

• 예를 들면 minheap에는 아래와 같은 순서로 정보가 저장되어있다.

• 아래 표에서는 알아보기 쉽게 편의상 (value, x[index]) 와 같이 index를 표현하려고 한다.

  x	y	z
  (-1, x[2])	(-15, y[0])	(-15, z[0])
  (10, x[3])	(-5, y[1])	(-15, z[1])
  (11, x[0])	(-4, y[3])	(-5, z[2])
  (14, x[1])	(-4, y[4])	(-1, z[3])
  (19, x[4])	(-1, y[2])	(19, z[4])

2. x, y, z에 대해서 edge를 만들고 edge에 대한 minHeap을 만든다.

• 예를 들면 아래와 같은 edge(거리, node1, node2)들이 하나의 minHeap에 담는다.

x	y	z
(-1-(10), 2, 3)	(-15-(-5), 0, 1)	(-15-(-15), 0, 1)
(10-(11), 3, 0)	(-5-(-15), 1, 3)	(-15-(-5), 1, 2)
(11-(14), 0, 1)	(-4-(-5), 3, 4)	(-5-(-1), 2, 3)
(14-(19), 1, 4)	(-1-(-4), 4, 2)	(-1-(19), 3, 4)

 

 

3. minHeap의 edge들을 하나씩 pop하여 MST를 만든다( 크루스칼 알고리즘을 활용 )

• 크루스칼 알고리즘 구현

하지만.. 실패...ㅠ

 

코드 - 실패

import heapq
from sys import stdin

def solution_BJ2887():
    n = int(stdin.readline())
    x, y, z = [], [], []
    edge_heap = []
    parent = [i for i in range(n)]
    rank = [0 for i in range(n)]
    total_value = 0
    num_of_edge = 0

    for i in range(n):
        tmp = stdin.readline().split()
        heapq.heappush(x, [int(tmp[0]), i])
        heapq.heappush(y, [int(tmp[1]), i])
        heapq.heappush(z, [int(tmp[2]), i])

    print('x : ', end =" "), print(x)
    print('y : ', end =" "), print(y)
    print('z : ', end =" "), print(z)

    make_edges(edge_heap, x)
    make_edges(edge_heap, y)
    make_edges(edge_heap, z)

    print('edge_heap : ', end =" "), print(edge_heap)

    while num_of_edge < n - 1:
        edge = heapq.heappop(edge_heap)
        if get_next_edge(edge, parent, rank):
            num_of_edge += 1
            total_value += edge[0]
            print(edge)
    print(total_value)
    return total_value

def make_edges(edge_heap, group):
    prev = heapq.heappop(group)

    while group:
        next = heapq.heappop(group)
        prev_val, next_val = prev[0], next[0]
        prev_idx, next_idx = prev[1], next[1]
        heapq.heappush(edge_heap, (abs(prev_val - next_val), prev_idx, next_idx))
        prev = next

def get_next_edge(edge, parent, rank):
    weight, node1, node2 = edge
    # if node1 > node2:
    #     node1, node2 = node2, node1

    if find(parent, node1) != find(parent, node2):
        union(rank, parent, node1, node2)
        return True
    return False

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

def union(rank, parent, node1, node2):
    root1 = node1
    root2 = node2

    if rank[root1] > rank[root2]:
        parent[root2] = root1
    else:
        parent[root1] = root2
        if rank[root1] == rank[root2]:
            rank[root2] += 1

if __name__ == '__main__':
    solution_BJ2887()