날마다 새로운 코딩

1. 문제 : https://www.acmicpc.net/problem/1185 1185번: 유럽여행 첫 줄에는 방문할 나라의 수 N(5 ≤ N ≤ 10,000)과 이 나라들 사이를 연결하는 길의 수 P(N-1 ≤ P ≤ 100,000)가 주어진다. 두 번째 줄에는 N+1번째 줄까지 i+1번째 줄에는 i번째 나라를 방문할 때 드는 비 www.acmicpc.net 2. 풀이 : Prim 3. 시간복잡도 : O(ElogV) 4. 설명 예제를 그림으로 표현하면 그림[1]과 같다. 모든 나라를 N-1개의 길 만으로 방문해야 하며, 그때의 비용이 최소가 되어야 하므로 MST를 생성해야 함을 알 수 있다. MST를 유지하며 시작 나라에서 모든 나라를 방문하고 시작 나라로 돌아오기 위해서는, 모든 도로를 2번씩 지나..

Algorithm/Prim 2021. 7. 2. 22:47

1. 문제 : https://www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net 2. 풀이 : Prim 3. 시간복잡도 : O(ElogV) 4. 설명 문제의 조건은 다음과 같다. 1. 처음 점거하고 있는 도시는 1번 도시이다. 2. 한번 정복한 도시는 다시 정복하지 않는다. 3. 도시를 정복한 후에는, 정복한 도시의 수 만큼 추가 비용이 발생한다. 4. 모든 도시를 최소의 비용으로 정복한다. 1, 2, 4 조건에 의해 1번 도시를 시작점으로하는 MST를 생성하고, ..

Algorithm/Prim 2021. 6. 13. 23:27

1. 문제 : 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 2. 풀이 : Prim 3. 시간복잡도 : O(ElogV) 4. 설명 그림[1]과 같이 주어진 그래프를 인접리스트로 표현한다. 시작점까지의 가중치는 없으므로 시작점의 번호인 7과 가중치 0을 우선순위큐에 삽입한다. 우선순위큐는 가중치의 오름차순으로 정렬한다. 그림[2]와 같이 7번 노드를 방문 처리 후, 7번 노드에서 갈 수 있는 노드의..

Algorithm/Prim 2021. 6. 7. 21:16