반응형
https://www.acmicpc.net/problem/1197
풀이 방법
- BFS 와 유사하다고 생각
- 하지만 간선은 양방향 그래프,
- heapq 를 사용 =>
from heapq import heappop, heappush
- heapq 의 특성을 이용하기 위해서 간선을 먼저 입력
- heappush(원소를 넣으려는 힙이름, (넣고자 하는 원소)
- heappop(원소를 빼려는 힙 이름)
- 방문 했는지 방문하지 않았는지 확인
- BFS의 방문처리와 유사함
- 어떤 간선의 정보를 입력해야 할까
- 쉽게 생각해보자 : 현재 위치한 그래프의 모든 간선
- 시간을 조금 줄여보자 : 현재 위치한 그래프의 간선 중 아직 방문하지 않은 간선
소스 코드
from heapq import heappop, heappush
def mst(start, weight):
Q = []
Q.append((weight, start))
visit = [0] * (V + 1)
cnt = V
ans = 0
while cnt != 0:
# 가중치, 현재위치
w, now = heappop(Q)
if visit[now] == 0:
visit[now] = 1
ans += w
cnt -= 1
for now, weight in G[now]:
heappush(Q, (weight, now))
return ans
V, E = map(int, input().split())
# G = [[0] * (V + 1) for _ in range(V + 1)]
G = [[] for _ in range(V + 1)]
for _ in range(E):
# 정점, 정점, 가중치
a, b, c = map(int, input().split())
G[a].append((b, c))
G[b].append((a, c))
# print(G)
print(mst(1, 0))
위의 풀이 방법과 동일함.
- 정점, 간선, 가중치 를 입력받음
- 각 그래프의 정점 위치에 간선 정보와 가중치 정보를 append
- 함수호출(시작 위치 = 1, 시작 가중치 = 0)
- Q 에 매개변수로 가져온 (가중치, 위치)를 입력
- 아직 방문하지 않은 위치
if visit[now] == 0:
이면 방문 - 가중치를 더해주고
- 현 위치의 모든 간선의 가중치와 번호를 넣음
- 반복이 끝나면 가중치의 합을 리턴
느낀점
- 힙큐 연습이 필요하다
반응형
'컴퓨터 > Algorithm' 카테고리의 다른 글
백준 26215 눈 치우기 (파이썬) (0) | 2023.01.18 |
---|---|
백준 2636 치즈 (파이썬) (0) | 2022.11.10 |
백준 5014 스타트 링크 (파이썬) (0) | 2022.10.13 |
백준 8979 올림픽 (파이썬) (0) | 2022.09.26 |
백준 10971 외판원 순회 2 (파이썬) (조합 생성방법) (0) | 2022.09.24 |