MST

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

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

[백준 1944] 복제 로봇 C++

1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 최소 스패닝 트리 - MST 현재 로봇이 복제를 거듭하며 열쇠를 찾으러 다니는 이동거리를 가장 작게 해야한다. 전체 이동거리를 가장 작게 해야하므로 다익스트라가 아니라 MST알고리즘을 사용해야 한다는걸 알았다. 입력을 받으면서 시작점과 모든 열쇠들은 정점이 되므로 정점 vector에 넣어준다. 정점들 간의 거리를 BFS를 통해 모두 구하고 간선의 정보를 저장한다. BFS 매번 돌면 자신을 제외하고 시작점을 포함한(M-1+1) M번 ..

[백준 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..