[BOJ/python]1922

백준 1922- 네트워크 연결
파이썬을 이용해 풀이를 했다

이전에 최소 스패닝 문제를 풀었는데 같은 문제라는 것을 알 수 있었다

최소 스패닝 트리

주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 값이 최소인 트리를 말한다

• 쉽게 말해 그래프를 지나기 위한 가중치 최소 합을 말하는 것이다
• 크루스칼 알고리즘, Prime MST 알고리즘을 많이 사용하는데 나는 Prime MST 알고리즘을 사용했다
• Prime MST 알고리즘은 현재 정점에서 다음 정점까지의 가중치가 가장 작은 정점을 선택해서 N개의 정점을 지날 때 까지 그래프를 확장해가는 방식이다
• 나는 여기에서 우선순위 큐를 이용해서 문제를 풀이했다

문제 풀이

최소 스패닝을 풀기 위해서 다음과 같은 과정을 거쳤다

1. 연결된 노드 a, 노드 b, 가중치 c가 주어질 때 각 노드별로 [가중치, 연결된 값] 정보를 저장해준다

   • 저장 시에는 양방향 그래프로 저장을 해줘야 한다
   • 가중치에 따라 우선순위가 매겨질 수 있도록 가중치를 우선해서 저장했다

2. 첫번째 값인 [가중치 0, node 1]을 우선순위큐의 첫번째 값으로 초기화 해준다

3. 우선순위큐에서 가중치가 가장 낮은 값을 꺼내고 만일 방문한 적이 없는 노드라면 현재 노드로 설정하고 방문처리를 해준다

   • answer(최소 가중치 합)에 현재의 가중치를 더해줍니다
   • cnt(거쳐온 노드 갯수)에 값을 하나 더해줍니다

4. 현재 노드에 연결된 [가중치, 다음노드] 값들을 우선순위 큐에 추가해준다

5. 3, 4번 반복

6. cnt(거쳐온 노드 갯수)가 N 값과 같다면 반복문을 멈추고 answer(최소 가중치 합)을 출력한다

코드

import heapq
from collections import defaultdict

def solution():
    N = int(input())
    M = int(input())

    C = defaultdict(list)
    
    for _ in range(M):
        a, b, c = map(int, input().split())
        C[a].append([c, b])
        C[b].append([c, a])

    heap = [[0, 1]]   
    visited = defaultdict(bool)
    answer, cnt = 0, 0

    while heap:
        now = heapq.heappop(heap)
        weight, node = now[0], now[1]

        if cnt == N:
            break
        
        if not visited[node] :

            visited[node] = True
            cnt += 1
            answer += weight

            for next in C[node]:
                heapq.heappush(heap, next)
    
    print(answer)

solution()

쟌쟌쟌

---

옛날에는 코드만 작성하고 끝났는데
면접에서 코테 때 짠 코드에 대해 설명하고 리팩토링을 해보라는 경우가 있었어서 정말 멘붕이 왔었다 흑흑...

그래서 앞으로는 왜 해당 자료구조/알고리즘을 썼는지에 대한 이유를 정리해보고
코드에 대해서도 절차적으로 설명 하는 연습을 해야겠다고 다짐했다