prim

[백준] 1922 네트워크 연결 | MST (Prim, Kruscal) | Gol4 Pythonhttps://www.acmicpc.net/problem/1922 접근유형 1 : MST - prim (396ms)유형 2 : MST - kruscal (240ms)간선 수가 노드수보다 100배 많은데 prim보다 kruscal 이 더 빠르네  [문제 해석]최소의 비용으로 모든 컴퓨터를 연결하는 경로 구하기= MST 최소 스패닝 트리 구하기1 1 1 간선이 주어질 때 두 노드번호가 같을 수도 있다 MST 프림으로 풀어보자~ 노드선택 구상 - Prim간선 입력받아서 연결된 첫번째 노드별로 (가중치, 노드2) 형태로 리스트에 저장최소힙 사용(정렬유지하며 잦은 삽입 필요)현재 그래프에 포함되어있는 노드 표시하는 배열..

[백준] 1197 최소 스패닝 트리 | MST(Prim) | Gol4 Pythonhttps://www.acmicpc.net/problem/1197 접근유형 : MST - 프림 알고리즘프림이 노드를 추가하는 방식이지만 결국은 간선의 가중치를 확인해야 하는데논리를 너무 노드에만 집중해서 생각했다. 생각을 열어두자~ [문제 해석]주어진 그래프의 최소 스패닝 트리MST를 구하는 문제 1 1 음수 가중치 간선 존재, 양방향 가중치 절댓값 시간 제한 1초 메모리 제한 128MB  [개념]MST 구하는 법 크루스칼 : 간선을 greedy로 선택, 사이클없이(union find)프림 : 노드를 선택. 노드 중 간선 가중치가 가장 적은 것정점보다 간선 개수 범위가 더 커서 프림으로 짜보자  구상 1 간선 입력받아 리스트..