Hoon222y

https://www.acmicpc.net/problem/1944 해당 문제의 경우 시작점과 키가 있는 지점간의 모든 거리를 구해두고 MST를 만들면 된다. 여기서 주의해야 할 점은 1) S와 K에서만 복제가 가능하기 때문에 57번째 줄 처럼 각각의 거리를 구할 때 K나 S에 도달했을 때에도 Queue에 넣어줘야 한다.2) 배열의 크기는 M이다 .... 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021..

https://www.acmicpc.net/problem/2887 모든 행성이 연결되는 MST를 만드는 문제이다. 하지만 보통 구하느 MST와는 다르게 N의 제한이 10만이기 때문에 모든 간선의 길이를 다 넣어주게 되면 O(N^2)으로 시간초과&메모리 초과 콤비를 맞게 될 것이다. 따라서 간선을 넣어줄 때 필요한 부분만 넣어주는 처리가 필요하다. 핵심은 거리가 Min(x절대값 차이, y절대값 차이, z절대값 차이) 이므로 각각 x,y,z를 기준으로 sort해준 다음 인전한 경우에만 거리를 넣어주는 3N의 시간복잡도를 넣어주게 되면 해결할 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484..

https://www.acmicpc.net/problem/6496497 MST를 만드는 문제이다.총 길이에서 MST를 만든 후 그 경로의 길이를 뺴주면 절약한 길이를 얻을 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include #include #include #include #include #include #include #include #include #include #define INF 1e9typedef long long ll;using namespace std; ll ans,t,n,m,parent[211111];vector..

MST 는 Minimum Spanning tree 인데 용어를 간략히 정리하자면 스패닝 트리 : 그래프에서 일부 간선을 선택해 만든 트리최소 스패닝 트리: 스패닝 트리 중에 선택한 간선의 가중치의 합이 최소인 트리 (트리의 정의 : 정점이 N개라면 간선은 N-1개인 경우 ) MST를 구현하는 방법에는 크게 3가지로 나누어 볼 수 있는데1) 프림 (Prim) - 정점을 중심으로 2) 크루스칼 (Kruskal) - 간선을 중심으로 3) 솔린 알고리즘 (sollin's algorithm)으로 나누어 볼 수 있다. 근데 보통은 같은 시작 복잡도를 가지고 있으므로 간단한 크루스칼을 많이 사용하는것 같다. 해당 포스팅에서는 크루스칼까지만 언급을 하도록 하겠다. 먼저 프림(Prim algorithm)의 경우1. 그래..