★[python_파이썬_pass]백준_16398번_행성 연결_MST_풀이

공부하는허딩크 : https://www.youtube.com/live/bsVMyjYPO3w?feature=shared

 

소요시간 약 30분

 

지난주 기본 MST알고리즘을 학습 하고 다시 문제를 보는데 알고리즘이 생각이 안나서 다시 복습하고 왔다.

https://heodinkcodingdiary.tistory.com/142

★[알고리즘 학습_MST_python_파이썬]백준_1197번_최소스패닝트리_MST_알고리즘 기초

 

일단 기초 문제 대비 행성간 비용이 행렬로 주어지기 때문에 그 입력 부분만 상황에 맞게 변경해 주었다.

(이것도 처음에는 이해가 안되서 고민을 많이 했다.)

 

<첫번째 시도 : 시간초과>

# 시간초과

# Cij가 N * N 행렬로 주어진다.

N = int(input())

graph = [[] for _ in range(N + 1)]

visited = [False] * (N + 1)

res = 0

# 주어진 행렬을 graph에 입력 : index행성 -> 0 : 비용, 1 : 연결행성

for i in range(N):

    cost = list(map(int, input().split()))

    for j in range(len(cost)):

        if i == j:

            continue

        else:

            graph[i + 1].append((cost[j], j + 1))

            #0번 index + 1 : 1번 행성으로 up

           

heap = [[0, 1]]

while heap:

    c, node = heapq.heappop(heap)

    if visited[node] == False:

        visited[node] = True

        res += c

    for next_node in graph[node]:

        if visited[next_node[1]] == False:

            heapq.heappush(heap, next_node)

           

print(res)

 

<두번째 시도 : 맞았습니다.>

첫번째 : while문 안에 for문의 들여쓰기를 잘못했다. => if문과 관계없이 실행되므로 visited와는 상관없이 for문이 돌아가서 불필요한 연산이 발생한다.

i == j인 경우도 추가해주면 조금 연산을 줄일 수 있다.

import sys

import heapq

input = sys.stdin.readline

# Cij가 N * N 행렬로 주어진다.

N = int(input())

graph = [[] for _ in range(N + 1)]

visited = [False] * (N + 1)

res = 0

# 주어진 행렬을 graph에 입력 : index행성 -> 0 : 비용, 1 : 연결행성

for i in range(N):

    cost = list(map(int, input().split()))

    for j in range(len(cost)):

        graph[i + 1].append((cost[j], j + 1))

        #0번 index + 1 : 1번 행성으로 up

       

heap = [[0, 1]]

while heap:

    c, node = heapq.heappop(heap)

    if visited[node] == False:

        visited[node] = True

        res += c

        for next_node in graph[node]:

            if visited[next_node[1]] == False:

                heapq.heappush(heap, next_node)

           

print(res)