https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net # 'N개의 행성을 터널로 연결하는데 필요한 최소비용' 보자마자 MST가 떠올랐다. # 처음에 N개의 행성 사이의 터널 건설비용을 모두 구한 뒤, 크루스칼 알고리즘을 사용하려 했다. 그런데, 모든 터널 건설비용을 구하기 위해선 N^2번의 연산이 필요하지만 N이 최대 10만이므로 이렇게 하면 시간초과가 발생한다. # A와 B 사이의 터널 건설비용은 min(|xA-xB..
https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net # 크루스칼을 이용한 MST로 풀었다. 1. 우선 N개의 좌표를 모두 입력받은 뒤, 좌표들끼리의 길이를 dist함수로 구한다. 2. graph에 (i, j, dist(i, j))를 넣어준다음 dist(i, j)순으로 오름차순 정렬해준다. 3. 이미 연결되어 있는 통로들은 union 해준 뒤 graph에서 연결이 안되어있는 통로들을 연결하며 answer에 길이를 더해준다...
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 # 무난한 MST문제이다. 마을을 두개의 마을로 분리하면서 남은 길들의 유지비가 최소가 되어야 하므로 크루스칼 알고리즘으로 최소 간선들로만 모든 집을 연결 한 뒤 가장 비용이 큰 길 하나만 없애면 된다. # 27 ~ 31줄 반복문에서 last는 항상 g[2]로 갱신되는데 graph가 비용순으로 오름차순 정렬되어 있으므로 결국 마지막 last에는 가장 비용이 큰..
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 # 문제를 보자마자 최소 스패닝 트리(Minimum Spanning Tree)가 떠올랐다. # 크루스칼 알고리즘으로 MST를 짰다. def solution(n, costs): answer = 0 # Union-Find함수 def find(c): if par[c] == c: return c else: par[c] = find(par[c]) return par[c] def union(a, b): a, b = find(a), find(b) par[max(a, b)]..
모르는 사이에 조금씩 조금씩..
