목차 최소 신장 트리 (MST, Minimum Spanning Tree) 그래프 내의 모든 정점을 포함하면서 사용된 간선들의 가중치 합이 최소가 되는 트리 MST 특징 1) 간선(Edge)의 가중치 합이 최소 2) N개의 정점을 가지는 그래프에서 반드시 (N - 1) 개의 간선만을 사용해야 함 (= 트리의 성질) 3) Cycle을 포함하면 안된다 프림(Prime) 알고리즘 - 인접 리스트와 우선 순위 큐, 그리고 방문 배열을 사용 - 시작점을 기준으로 인접한 정점 중에 아직 연결하지 않았고, 가중치가 최소인 정점을 선택 반복하여 노드를 연결함 - 우선 순위 큐를 집합으로 보고, 가장 가중치가 작은 노드를 우선 순위로 하여 연결(=방문) 여부 확인 후 연결 처리 한다. - 시간 복잡도 : O((V + E)..

최소 신장 트리 (MST, Minimum Spanning Tree) 그래프 내의 모든 정점을 포함하면서 사용된 간선들의 가중치 합이 최소가 되는 트리  MST 특징1) 간선(Edge)의 가중치 합이 최소2) N개의 정점을 가지는 그래프에서 반드시 (N - 1) 개의 간선만을 사용해야 함 (= 트리의 성질)3) Cycle을 포함하면 안된다  크루스칼(Kruskal) 알고리즘 - 최소 신장 트리(MST)를 구하는 알고리즘 중 하나- 매 순간 최소 가중치를 가지는 간선을 선택하여 연결하므로, 탐욕 알고리즘으로도 분류됨- 이때 Union-Find 알고리즘과 함께 사용하여 Cycle 형성되지 않을 경우 노드를 연결한다- 시간복잡도 : O(ElogE) - 실제 로직보다 간선 정보 정렬시 비용이 가장 큰 걸로 알려져..

문제 링크 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 문제 풀이 - 크루스칼 알고리즘으로 풀이시 메모리 초과 발생 - 행성의 개수 N이 최대 10^5 일 때 2중 for문 순회하면서 cost 연산 후 edge 추가시 최대 10^5 * 10^5 (러프하게 해석, 중복 제외시 연산은 더 적음)이고, Edge의 경우 class Edge {int from, int to, long cost} 로 정의시 (4byte ..

문제 링크 https://www.acmicpc.net/problem/20010 20010번: 악덕 영주 혜유 FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때, www.acmicpc.net 문제 풀이 최소 가중치를 가지는 MST는 구했는데, 두번째 값을 구하지 못해 3시간을 소비했다. 찾아본 결과 트리의 지름을 구하는 방법을 몰랐고, 문제 지문을 제대로 읽지 못해 MST 트리 정보를 활용하는 것을 파악하지 못했다..(반성) 문제 지문을 다시 보면 아래와 같다 마음이 괘씸한 혜유는 돈을 최대한 적게 쓰면서 퀘스트를 달성하려고 한다. 혜유를 도와서 (1)모든 마을과 마을을 ..

문제 링크 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제 풀이 - 별자리(노드)를 모두 연결하는 최소 비용을 구하는 문제 - 프림 알고리즘으로 풀이 (최소신장트리, MST) - 시간 복잡도 : O(ElogV) 1) 2차원 좌표로 입력 주어지는데 각각 노드 1, 2, .. 로 보고 노드별 거리 값을 계산하여 컬렉션에 담는다 (양방향 그래프) 2) 시작 노드는 1로 고정해서 프림 알고리즘 수행 - 방문한적 있으면 continue; - 방문한적..

문제 링크 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 문제 풀이 그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다. 위의 지문이 조금 이해가 안되었는데, 사이클이 발생하는 경우에 대해 설명하는 것으로 이해했다. - 크루스칼/프림 알고리즘 (최소 신장트리,MST) 사용하여 최소 비용을 구한 후 전체 비용과의 차..

문제 링크 https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 문제 풀이 크루스칼 알고리즘을 사용하기 위해 노드와 노드 사이의 비용 정보가 필요한데, 2차원 좌표(X, Y)가 주어질 때 노드로 생각하지 못했고, 거리 계산 또한 생각을 하지 못했다. 해당 문제를 통해 시야가 또 좁아진 점을 반성한다.. 입력 예시 4 1 // 노드 수, 연결된 노드 수 1 1 // 노드 1 3 1 // 노드 2 2 3 // 노드 3 4 3 ..