대표적인 최소 스패닝트리 프림 알고리즘 우선순위 큐 대신 이진탐색 트리 이용
출처 : 네트워크 연결 acmicpc.net/problem/1922
| 시간 제한 | 메모리 제한 |
|---|---|
| 2초 | 256 MB |
문제
도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)
그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다.
입력
첫째 줄에 컴퓨터의 수 N (1 ≤ N ≤ 1000)가 주어진다.
둘째 줄에는 연결할 수 있는 선의 수 M (1 ≤ M ≤ 100,000)가 주어진다.
셋째 줄부터 M+2번째 줄까지 총 M개의 줄에 각 컴퓨터를 연결하는데 드는 비용이 주어진다. 이 비용의 정보는 세 개의 정수로 주어지는데, 만약에 a b c 가 주어져 있다고 하면 a컴퓨터와 b컴퓨터를 연결하는데 비용이 c (1 ≤ c ≤ 10,000) 만큼 든다는 것을 의미한다. a와 b는 같을 수도 있다.
출력
모든 컴퓨터를 연결하는데 필요한 최소비용을 첫째 줄에 출력한다.
아이디어
-
우선순위 큐를 이용한 프림 알고리즘 구현
힙 이라는 자료구조를 이용해, 반정도 정렬된 구조에서 항상 최대 또는 최소를 찾을 수 있다는 장점이 있다. 삽입, 삭제 모두 O(logN)이라는 시간 복잡도를 가지며, 완전한 정렬상태를 가지지 않아 시간복잡도에서 이점을 가진다. 다만, 탐색은 O(N)이라는 시간복잡도를 가진다.시간 복잡도 공간 복잡도 O(ElogE) (E + V) * (sizeof)int + ɑ -
BST(Binary Search Tree)를 이용하여 프림 알고리즘 구현
힙과 같은 2진트리이며, 이진트리는 삽입, 삭제, 탐색이 최소 O(logN)에서 O(N)의 시간복잡도를 가진다. 다만, 자바 콜렉션 프레임워크에서는 TreeMap, TreeSet은 O(logN)의 시잔복잡도를 삽입, 삭제, 탐색에 모두 보장한다.TreeSet.java A NavigableSet implementation based on a TreeMap. The elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used. This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).출처 : 자바 공식 문서
삽입, 삭제, 탐색 과정에서 AVL트리처럼 균형 이진트리를 유지하는것으로 추정된다.
따라서, 힙 자료구조보다는 균형을 유지하기 위해 추가적인 삽입, 삭제에 조금 더 오래걸릴 것으로 추정되지만, 탐색 또한 O(logN)이라는 시간복잡도를 가진다는 장점이 있다.시간 복잡도 공간 복잡도 O(ElogV) (E + V) * (sizeof)int + ɑ
코드
우선순위 큐를 이용한 프림 알고리즘
백준에서 코드 보기 : http://boj.kr/578f96de5024454282bcb510e297c6d7
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static class Node implements Comparable<Node>{
public int to;
public int weight;
public Node(int to, int weight) {
this.to = to;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
return Integer.compare(this.weight,o.weight);
}
}우선순위 큐에 넣어 줄 노드의 우선순위를 재정의
private static ArrayList<Node>[] weights;
private static boolean[] visit;
private static int V,E;
private static int primPQ(int start){
PriorityQueue<Node> pq = new PriorityQueue<>();
int total = 0;
pq.offer(new Node(start,0));
while (!pq.isEmpty()){
Node node = pq.poll();
if (visit[node.to])
continue;
total += node.weight;
visit[node.to] = true;
for (int i = 0; i < weights[node.to].size(); i++) {
Node next = weights[node.to].get(i);
if (!visit[next.to])
pq.add(next);
}
}
return total;
}방문하지 않았던 모든 노드 까지의 가중치를 우선순위큐에 삽입해, 이후 방문 후 큐에서 뽑으면 continue를 통해 다시 뽑음.
필요하지 않은 노드들이 우선순위 큐에 들어있어 깊이를 깊게하여 삽입삭제 시간을 높힘.
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
V = Integer.parseInt(br.readLine());
E = Integer.parseInt(br.readLine());
visit = new boolean[V];
weights = new ArrayList[V];
for (int i = 0; i < V; i++) {
weights[i] = new ArrayList<>();
}
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken())-1;
int to = Integer.parseInt(st.nextToken())-1;
int weight = Integer.parseInt(st.nextToken());
if (from == to)
continue;
weights[from].add(new Node(to,weight));
weights[to].add(new Node(from,weight));
}
System.out.println(primPQ(0));
}
}
이진 탐색 트리를 이용한 프림 알고리즘
백준에서 코드 보기 : http://boj.kr/467b9ee3110e4fbf8c24e5cc8a4f7cb5
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static class Node implements Comparable<Node>{
public int to;
public int weight;
public Node(int to, int weight) {
this.to = to;
this.weight = weight;
}
@Override
public boolean equals(Object obj) {
Node node = (Node)obj;
if (this.weight == node.weight && this.to == node.to)
return true;
else
return false;
}
@Override
public int compareTo(Node o) {
if (this.weight == o.weight)
return Integer.compare(this.to,o.to);
else
return Integer.compare(this.weight,o.weight);
}
}TreeSet은 중복값을 허용하지 않는다. HashSet은 해시코드를 이용해서 해싱을해서 같은 값을 가지더라도, 다른 해시코드값을 가지면 다르게 구분되지만, TreeSet은 값만 비교해서 같은값이면 다른 해시코드라도 같은곳에 저장된다. 따라서, 가중치값이 같더라도 다르게 구분하기 위해 노드값 또한 compareTo 매소드에 비교하게 해줬다.
TreeSet은 내부적으로 같은지 비교하기위해 equals 매소드도 많이 호출한다. 따라서, equals매소드도 필요에따라 Override해줬다.
private static ArrayList<Node>[] weights;
private static int[] distance;
private static boolean[] visit;
private static int V,E;
private static int primBST(int start){
TreeSet<Node> treeSet = new TreeSet<>(); // Node(to, weight)
int total = 0;
distance[start] = 0;
treeSet.add(new Node(start,0));
while (!treeSet.isEmpty()){
start = treeSet.pollFirst().to;
total += distance[start];
visit[start] = true;
for (int i = 0; i < weights[start].size(); i++) {
Node node = weights[start].get(i);
if (!visit[node.to] && distance[node.to] > node.weight){
if (distance[node.to] == Integer.MAX_VALUE) { // never was in tree;
distance[node.to] = node.weight;
treeSet.add(node);
}
else { // is in tree;
treeSet.remove(new Node(node.to, distance[node.to]));
distance[node.to] = node.weight;
treeSet.add(node);
}
}
}
}
return total;
}TreeSet에는 방문하지 않았던 노드들만 저장되어있어 최대 깊이는 logV이며, 탐색이 가능해 가중치를 갱신하기 위해 remove와 add를 적절히 활용해 낮은 깊이를 유지함에 시간복잡도에 이점이 생기고, 메모리 또한 이점생기지만, distance배열을 추가해 비슷할거 같다.
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
V = Integer.parseInt(br.readLine());
E = Integer.parseInt(br.readLine());
distance = new int[V];
Arrays.fill(distance,Integer.MAX_VALUE);
visit = new boolean[V];
weights = new ArrayList[V];
for (int i = 0; i < V; i++) {
weights[i] = new ArrayList<>();
}
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken())-1;
int to = Integer.parseInt(st.nextToken())-1;
int weight = Integer.parseInt(st.nextToken());
if (from == to)
continue;
weights[from].add(new Node(to,weight));
weights[to].add(new Node(from,weight));
}
System.out.println(primBST(0));
}
}
결론
우선순위 큐와 TreeSet은 각각 힙과 균형이진트리라는 자료구조형태로 구현되어있어, 둘 다 이진트리라는 공통점이 있다.
힙은 반정도만 정렬되어 삽입 삭제가 빠르고 최대 또는 최소를 항상 알 수 있는 장점이 있다.
단점으로는 탐색을 하기위해서는 모든 값을 다 비교해야하므로 O(N)이라는 시간 복잡도를 가지는 단점이 있고, 완전히 정렬된 상태가 아니다.
균형 이진 트리는 완전 정렬되어 삽입 삭제 탐색까지 모두 O(logN)이라는 시간 복잡도를 가진다는 장점이 있다.
단점으로는 균형을 유지하기 위해 삽입 삭제 과정에 추가적인 연산이 필요 할 수 있다는 장점이 있다.
해당 문제에서 힙은 빠른 삽입 삭제로 문제를 풀 수 있었지만, 탐색을 못해 깊이 조절이나, 필요없는 값 까지 들어가게 되었다.
하지만, 균형 이진트리는 빠른 삽입 삭제와 탐색을 통해 필요한 값만 트리에 담아 깊이를 조절하고 필요없는 값을 넣지 않을 수 있었으나 추가적으로 distance라는 배열을 활용하게 된다는 점에서 메모리가 더 사용되었다.
힙과 균형이진트리의 장단점을 잘 비교 할 수 있었고, 앞으로 상황에 따라 더 최적화된 자료구조를 선택 할 수 있게 되었다.
