최소 스패닝 트리

[백준 1368] 물대기 (C++)

1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 모든 논을 최소 비용으로 연결시키는 문제이다. 따라서 최소 스패닝 트리라고 생각할 수 있다. 문제의 핵심은 이미 물이 있는 논을 통해서만 물을 댈 수 있다는 것이다. 그래서 어렵게 생각한다면 우물을 파는데 가장 비용이 적은 논을 구하고.. 그 논을 통해서 가장 비용이 적은 간선을 선택하고.. 등등 케이스가 복잡한 상황이 정말 많이 생길 것이다 다익스트라에서 주로 사용했었던 방식인데 가상 노드를 하나 설정한다. 가상 노드는 논들과 연..

[백준 17472] 다리 만들기 2 (C++)

17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net BFS, 최소 스패닝 트리 BFS를 통해서 각 칸마다 섬의 번호를 지정해서 섬을 구분한다. 모든 섬과 섬 사이의 거리를 구한다. 서로 이어지지 않은 섬은 거리를 INF로 한다. 여기까지 사전작업을 마쳤으면 모든 섬을 연결하는 최소 거리를 구하면 된다. 모든 노드를 연결하는 최단거리를 구하는 알고리즘은 최소 스패닝 트리임을 알 수 있다. 2번 과정에서 얻은 섬 간의 거리는 양방향이었으므로 중복되는 구간은 제외하고 새로운 벡터에 넣어준다. 거리를..

[백준 1774] 우주신과의 교감 C++

1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 최소 스패닝 트리 Minimum Spanning Tree (MST) - Kruskal 크루스칼 알고리즘(Kruskal Algorithm)을 활용한 최소 스패닝 트리 구하기 모든 간선(Edge)에 대해 가중치가 가장 작은 간선부터 이어나가면서 최소 스패닝 트리를 구하는 알고리즘이다. 유니온 파인 hyeo-noo.tistory.com 통로의 개수 1000개 이미 연결이 되어있다고 입력받은 노드들끼리는 Union_Node를 수행한다. adj..

근거리 네트워크 (LAN)

algospot.com :: LAN 근거리 네트워크 문제 정보 문제 근거리 네트워크(LAN, Local Area Network)는 가정, 학교, 혹은 회사 등의 제한된 공간 내의 컴퓨터들을 연결하는 네트워크입니다. 알고스팟 대학교에서는 캠퍼스의 일 algospot.com 최소 스패닝 트리 문제 설명 더보기 N개의 정점의 좌표가 주어지고 가중치 없이 연결할 수 있는 정점의 번호가 주어진다. 양방향 간선이지만 u에서 v로 가는 간선 하나만 저장해주면 된다. (u < v) 2중 for문을 통해서 모든 정점끼리 연결될 수 있는 가중치가 포함된 간선을 구해준다. 크루스칼 알고리즘을 적용하기 전에 주어지는 정점들을 Union해버리면 가중치 없이 정점을 미리 연결해줄 수 있다. 그리고 나머지 정점들을 크루스칼 알고리..

Minimum Spanning Tree (MST) - Kruskal

크루스칼 알고리즘(Kruskal Algorithm)을 활용한 최소 스패닝 트리 구하기 모든 간선(Edge)에 대해 가중치가 가장 작은 간선부터 이어나가면서 최소 스패닝 트리를 구하는 알고리즘이다. 유니온 파인드(Union-Find)에 대한 이해 8할 Edge 구조체 설계 2할? find_topnode() 를 통해서 현재 정점(Vertax)의 최상단 노드(부모노드) 를 알 수 있다. Node[Vertax]의 값이 음수이면 Vertax가 부모노드임을 의미한다 is_cycle()을 통해서 a와 b 정점이 서로 같은 노드인지 확인한다(find_topnode() 사용) Union_node()를 통해서 a 와 b정점을 하나로 병합한다 a, b정점의 부모 노드가 가지는 값은 항상 음수이다. 값이 더 작을수록 더 많은..