시나위

1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 문제 요약 모든 컴퓨터를 연결하는데 필요한 최소 비용을 출력한다. 접근 1. BFS 최소 비용이면 BFS라고 생각할수 있겠지만 시작점에서 특정 지점까지의 최소 거리이므로 조건과 맞지않다. (몇몇 조건은 만족할수 있다.) 2. MST(Minimum Spanning Tree) 최소신장트리 사용된 간선들의 가중치 합이 최소인 트리이다. 신장트리를 만들때 최소의 간선을 사용해서 모든 노드를 방문해야 하고, 사이클을 만들지 않아야한다. Kruskal 낮은 비용의 간선부터 차례로 선택함 사이클이 생기는 간선은 제거함(cycle이 만들어지는지 확인 필요, ex. ..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 백트래킹 문제를 풀다가 계속 틀려서 쉬운문제를 하나 가져왔다. 최소 신장 트리를 구하는 문제이고 prim 알고리즘을 사용해서 풀었다. 다익스트라랑 크게 차이가 없는듯 하다. from heapq import heappop, heappush def mst(g): ret = 0 visit = [0 for _ in range(len(g))] h = [(0, ..

https://programmers.co.kr/learn/courses/30/lessons/42861# 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 프림 알고리즘으로 풀었다. 크루스칼로도 풀어도 될듯 from heapq import heappop, heappush def solution(n, costs): answer = 0 adj_list = [[] for _ in range(n)] for s, e, c in costs: adj_list[s].append((c, e)) adj_list[e].append((c, s)) # prim visit = [0 for _ in range(n)] h = [(0, 0)..

https://www.acmicpc.net/problem/21924 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 최소 신장 트리 문제이다. Prim 알고리즘으로 풀었다. 인접한 정점(건물)을 추가하는 연결리스트를 만들고 신장트리를 만든다. 그리고 최소 값인 도로끼리 연결해야하므로 heap 자료구조를 사용한다. 신장트리는 정점 1부터 시작해서 인접하되 방문하지 않은 정점들을 추가한다. h..