Doby's Lab

https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 별자리를 트리라고 생각했을 때, 거리 값이 비용 값이고, 총비용이 최소가 되게 구하려면 최소 스패닝 트리를 이용하면 된다. 생각을 해야 했던 부분은 각 별(노드)끼리의 거리였다. 복잡하게 생각할 필요 없이 2중 for문을 이용해 쌍방향으로 최소 스패닝 트리를 할 수 있도록 만들어주었다. for(int i = 0; i < v.size(); i++){ for(int j = 0; j < v.size();..

https://www.acmicpc.net/problem/16202 16202번: MST 게임 첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있 www.acmicpc.net MST의 조건인 간선의 개수가 N - 1이 되지 않는다면 0을 출력해주면 된다. 가중치가 작은 간선부터 제외시키는 방법은 for의 범위를 조금씩 높이면 된다. [AC 코드] #include #include #include #include #define MAX (100000 + 1) #define pii pair #define ll l..

https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 그래프에서 전체적인 관점에서 보았을 때, 가중치의 합들이 최소가 되게 하는 문제다. >> MST 사용 >> 크루스칼 [AC 코드] #include #include #include #include #define MAX (100000 + 1) #define pii pair #define ll long long using namespace std; vector edges; int parent[MAX]; int n, m; bool cmp(pair a, pair b) { return a.seco..

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 최소 스패닝 트리를 2개 가져야 하는데라고 생각하면 머릿속에 생각되는 트리 2개의 그림 때문에 접근이 어려웠다. 하지만, 문제에서 이 조건을 잘 봐야 한다. "마을에는 집이 하나 이상 있어야 한다." 이 말은 마을에 집이 하나만 있으면 된다고 말하는 것과 같다. 즉, 최소 스패닝 트리를 구하되 마지막 노드를 포함시키지 않는다면 두 마을이 형성될뿐더러 남아있는 ..

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 공부한 블로그 (https://ansohxxn.github.io/algorithm/mst/) (https://yabmoons.tistory.com/186) [개요] 최소 스패닝 트리란? 방향이 없다. (양방향) 사이클이 없다. >> 트리라고 부르는 이유 모든 노드가 연결되어 있다. (간선이 없는 노드가 존재하면 안 된다.) 트리의 모든 가중치의 합이 ..