백준 / 1197번 최소 스패닝 트리 - 힙,해시 / Python 파이썬

 

*문제 출처는 백준에 있습니다.

문제 제목: 최소 스패닝 트리 

문제 사이트: https://www.acmicpc.net/problem/1197

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

예제 입력 1 복사

3 3
1 2 1
2 3 2
1 3 3

예제 출력 1 복사

3

---

나의 풀이

 

힙 써야됨.. 일반 bfs 처럼 생각해서 매번 sort 하면 시간 복잡도가 커져서 비교적 시간복잡도가 낮은 힙 이용

 

maps 로 간선 노트표현 -> 인덱스 자체가 몇번째 노드인지 정의하고있음. 

 

제일 처음 노드를 cost 0, next node 1 로 했을때,

1번째 노드에서 방문처리 확인 및 처리 후 cost 를 answer += 1 해줌

그리고 1번째 노드와 연결된 노드를 확인 후 힙push 로 넣어서 최소 비용으로 갈 수 있는 다음 간선을 넣기 (방문처리 확인도 해야함)

반복함

import sys
import heapq as hq

input = sys.stdin.readline

N, M = map(int, input().split())
maps = [[] for i in range(N+1)]
visited = [False] * (N+1)

answer = 0
for _ in range(M):
    A, B, C = map(int, input().split())
    maps[A].append((C,B)) # 비용, 다음 간선
    maps[B].append((C,A))
queue = [(0,1)]
while queue:
    q = hq.heappop(queue)
    # 현재 노드 방문처리
    if visited[q[1]] == True:
        continue
    elif visited[q[1]] == False:
        answer += q[0]
        visited[q[1]] = True
    # 현재 노드와 이어져 있는 간선 확인 *
    for next_c, next_node in maps[q[1]]:
        if not visited[next_node]:
            hq.heappush(queue, (next_c,next_node))


print(answer)

인덱스 처리랑 방문처리 잘 하자.

딕셔너리로 간선 표현해버리면 딕셔너리 안에서 애들 비었는지 확인하는것도 걸려서 시간 복잡도 높아짐

 

 BFS와 Prim 알고리즘의 차이

BFS는 모든 노드를 같은 거리 기준으로 탐색하는 데에 중점을 둔다. 간선의 가중치를 고려하지 않기 때문에, 최소 비용으로 연결하는 데는 적합하지 않다.

반면 Prim 알고리즘은 최소 신장 트리(MST)를 만들기 위해, 현재 연결된 노드들 중 가장 비용이 낮은 간선을 선택한다. 이 과정에서 우선순위 큐를 사용하여 최소 비용 간선을 빠르게 선택한다.

---

방문처리 안하면 시간 초과 발생함

Prim 알고리즘 구현에서 큐에 이미 방문한 노드로 향하는 간선이 계속 추가되면, 같은 노드가 중복으로 큐에 들어가 연산이 많아지고 시간 초과가 발생한다. 이를 방지하려면 heappop() 후, 해당 노드가 이미 방문되었는지 확인하고 continue 해야 한다.

 

힙 함수 정리

import heapq

heap = []

heapq.heappush(heap, (cost, node))     # 최소 힙에 값 추가
cost, node = heapq.heappop(heap)       # 가장 작은 값 꺼내기
heapq.heapify(arr)                     # 리스트를 힙으로 변환
heap[0]                                # 힙에서 가장 작은 값 확인 (삭제 안 함)

---

※ 알아야 할 것

• BFS는 거리 기반 탐색, Prim은 비용 기반 선택
• MST 문제는 Prim 또는 Kruskal 알고리즘으로 해결
• 우선순위 큐 사용 시 중복 방문 방지 필수
• 매번 sort()보다 heapq가 더 효율적이다 (O(log N))