힙큐

[python] SWEA - 1249. 보급로 / 5521. 상원이의 생일파티

1. 보급로 문제 해결 1. 다익스트라 알고리즘 + 힙큐 2. 가중치 리스트와 방문 리스트를 만들어 준다. 3. 힙큐를 이용해 가중치가 가장 낮은 점을 선택하고 4. 주변을 탐색하여 최소 가중치를 선택해 가중치를 점점 누적해 나아간다. 소스 코드 import heapq for tc in range(1, 1+int(input())): n = int(input()) maps = [list(map(int, list(input()))) for _ in range(n)] # dist: 가중치를 누적한 리스트, visit: 선택했는지 안했는지 dist = [[float('inf')]*n for _ in range(n)] visit = [[False]*n for _ in range(n)] dx, dy = [-1, 1..

[python] 백준 - 1922. 네트워크 연결

문제 해결 1. 오늘 배운 최소 신장 트리(MST)를 사용하는 그래프 문제다. ( + heapq 모듈 사용 ) 💨 그래프에서 사이클을 제거하고 모든 노드를 포함하는 트리를 구성할 때, 가중치의 합이 최소가 되도록 만든 경우를 최소신장트리라고 한다. (1) 먼저 간선과 가중치를 인접리스트로 만든다. (2) key, mst, pq | 최소 가중치를 갱신하는 배열, 방문 배열, 힙큐( 최소값을 뽑는 모듈 ) 2. 시작점( 노드중 아무거나 )을 힙큐에 넣어주고 시작 - 이 문제에서는 모든 노드를 연결할 수 있다. (1) 힙큐 안에서 가중치가 가장 낮은 정점을 pop (2) 방문했는지 확인 | 이미 방문을 했다면 continue 를 통해 힙큐에서 다시 뽑고, 아니라면 True로 바꿔주고 가중치를 결과에 더해준다...