MST

[백준] 14621 나만 안되는 연애 | MST (Kruscal) | Gol3 Pythonhttps://www.acmicpc.net/problem/14621 접근유형 : MST - kruscal  [문제해석] 모든 대학교를 연결하는 최단경로 = MST 남초대학교M 와 여초대학교W 사이의 간선만 경로에 포함할 수 있음 모든 학교를 연결하는 경로가 존재하지 않을 경우 -1 출력 1 1 크루스칼~로 해보자 간선수 노드수에 비해 그렇게 많은 것같진 않고 프림보다 빠른 편이니까특이사항은 간선 선택할 때, 연결된 노드의 학교종류가 같으면 선택하지 않도록 짜면 될 듯  구상 간선 (가중치, 노드1, 노드2) 형식으로 한 리스트에 입력받음 이 때 노드1과 노드2의 학교타입이 같으면 리스트에 넣지 않음 (그래프에 사용할..

[백준] 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 (Kruscal, Union Find) | Gol4 Pythonhttps://www.acmicpc.net/problem/1197 접근유형 : MST - 크루스칼 알고리즘크루스칼 알고리즘은 간선 추가 시마다 사이클이 생기는 지 확인하기 위해 주로 Union Find를 사용한다. 그래서 그 내용도 나옴! [문제 해석]주어진 그래프의 최소 스패닝 트리MST를 구하는 문제1 1 음수 가중치 간선 존재, 양방향가중치 절댓값 시간 제한 1초메모리 제한 128MB [개념]MST 구하는 법크루스칼 : 간선을 greedy로 선택, 사이클없이(union find)프림 : 노드를 선택. 노드 중 간선 가중치가 가장 적은 것 직전 글에 프림으로 풀어보았고, 이번에는 크루스칼로 풀..

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