★[python_파이썬_pass]백준_1922번_네트워크 연결_MST_풀이

공부하는허딩크 : https://www.youtube.com/live/0i-zE5mSAH0?feature=shared

 

일단 기본 알고리즘 코드를 외우고 나서 시도를 해서 한번에 통과가 되었다.

 

MST알고리즘 학습 : https://heodinkcodingdiary.tistory.com/142

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

 

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

알고리즘 학습 기본 코드를 그대로 활용했다. 

heapq라이브러리를 활용해서 노드간 연결 비용의 최소값이 먼저 나오게 구성하면서 해결 할 수 있었다.

import sys

import heapq

input = sys.stdin.readline

N = int(input())

M = int(input())

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

visited = [False] * (N + 1)

result = 0

for _ in range(M):

    a, b, c = map(int, input().split())

    graph[a].append([c, b])

    graph[b].append([c, a])

# graph = [[],

#         [[5, 2], [4, 3]],

#         [[5, 1], [2, 3], [7, 4]],

#         [[4, 1], [2, 2], [6, 4], [11, 5]],

#         [[7, 2], [6, 3], [3, 5], [8, 6]],

#         [[11, 3], [3, 4], [8, 6]],

#         [[8, 4], [8, 5]]]

heap = [[0, 1]] #가중치, 시작 node

#노드를 돌면서 방문한 적이 있는 노드는 제외

while heap:

    w, node = heapq.heappop(heap)

    if visited[node] == False:

        visited[node] = True

        result += w

        for next in graph[node]: #graph[1] = [[5, 2], [4, 3]] next = [5, 2]

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

                heapq.heappush(heap, next)

               

print(result)

 

heapq.heappop으로 빼기를 해주면 w값이 가장 작은 요소부터 나온다.

"""

첫번째 graph[1] heap = [[5, 2], [4, 3]] re = 4

두번째 graph[3] heap = [4, 1], [2, 2], [6, 4], [11, 5], [5, 2] re = 4+2

    [4, 1] if불만족

세번째 graph[2] heap = [5, 1], [2, 3], [7, 4], [6, 4], [11, 5], [5, 2]

    [5, 1], [2, 3], [5, 2] if불만족 re = 4 + 2 + 6

네번째 graph[4] heap = [7, 4], [11, 5], [7, 2], [6, 3], [3, 5], [8, 6]

    [7, 4], [7, 2], [6, 3] if불만족 re = 4 + 2 + 6 + 3

5. graph[5] heap = [11, 5], [8, 6], [11, 3], [3, 4], [8, 6]

    [3, 4], [11, 3], [3, 4] if불만족 re = 4 + 2 + 6 + 3 + 8 = 23

6. graph[6] heap = [8, 4], [8, 5]

    모두 if불만족

"""

 

<스터디원 코드 : kruskal / union-find알고리즘 활용 풀이>

1. queue변수에 c를 기준으로 최소값이 앞으로 나오게 sort를 해준다.

2. 그뒤 많이 복잡하네. 다시 복습 필요

import sys

input = sys.stdin.readline

n = int(input())

m = int(input())

queue = []

for _ in range(m):

    a, b, c = map(int, input().split())

    queue.append((c, a, b))

queue.sort()

parent = [i for i in range(n+1)]

def find(x):

    if parent[x] == x:

        return parent[x]

    parent[x] = find(parent[x])

    return parent[x]

def union(a, b):

    a = find(a)

    b = find(b)

   

    if a > b:

        parent[a] = b

    else:

        parent[b] = a

answer = 0

for cost, a, b in queue:

    if find(a) != find(b):

        union(a, b)

        answer += cost

print(answer)

 

이거 조금 복잡하네.... 나중에 다시 복습해보자.

parent = [0, 1, 2, 3, 4, 5, 6]

1. [2, 2, 3]

if find(2) != find(3):

    find(2)

    if parent[2] == 2: return parent[2] => 2

    find(3)

    if parent[3] == 3: rerutn parent[3] => 3

union(2, 3)

a = 2

b = 3

parent[3] = 2

parent = [0, 1, 2, 2, 4, 5, 6]

answer = 2

2. [3, 4, 5]

if find(4) != find(5) : return 4, 5

union(4, 5)

a = 4

b = 5

parent[5] = 4

parent = [0, 1, 2, 2, 4, 4, 6]

answer = 2 + 3

3. [4, 1, 3]

if find(1) != find(3) : retrurn 1, 2

union(1, 2)

parent[2] = 1

parent = [0, 1, 1, 2, 4, 4, 6]

answer = 2 + 3 + 4

4. [5, 1, 2]

if find(1) != find(2) : return 1, 1

5. [6, 3, 4]

if find(3) != find(4) : return 2, 4

union(3, 4)

a = 2

b = 4

parent[4] = 2

parent = [0, 1, 1, 2, 2, 4, 6]

answer = 2 + 3 + 4 + 6

6. [7, 2, 4]

find(2) , find(4) : return 1, 1

7. [8, 4, 6]

find(4), find(6) : return