문제
도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)
그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다.
풀이
나는 다익스트라 알고리즘을 조금 응용해서 풀었다.
다익스트라 알고리즘은 한 노드에서 모든 노드를 방문할 때 노드를 방문하는 최소거리를 구하는 알고리즘이다.
이 문제에서는 누적거리가 필요한 것이 아닌 각각의 노드를 모두 방문 할 때, 최소비용을 구하는 문제다.
따라서 누적합이 아닌 그냥 최소거리를 넣어두고 모두 더하는 방식으로 풀었다.
기존의 다익스트라를 통해 예제를 풀경우
| 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 5 | 4 | 10 | 13 | 18 |
이렇게 dist 배열이 나오게 된다.
하지만 나는 이 방식이 아닌 그 노드를 방문하는 최소 비용을 저장했기 때문에
| 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 2 | 4 | 6 | 3 | 8 |
dist 배열이 위와 같이 나오고 총합은 23이 나오게 된다.
정답을 맞고 보니 이문제의 정식 풀이는 아니었다.
<내가 푼 코드>
import java.io.*;
import java.util.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static int[][] map;
static boolean[] visited;
static class vertex implements Comparable<vertex>{
public int v;
public int weight;
public vertex(int v, int weight) {
this.v = v;
this.weight = weight;
}
@Override
public int compareTo(vertex v1) {
// TODO Auto-generated method stub
return this.weight - v1.weight;
}
}
public static void main(String[] args) throws IOException{
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(bufferedReader.readLine());
int m = Integer.parseInt(bufferedReader.readLine());
map = new int[n + 1][n + 1];
for(int i = 0 ; i < m ; i++) {
StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
map[a][b] = w;
map[b][a] = w;
}
int[] dist = new int[n + 1];
for(int i = 1 ; i < n + 1; i++) {
dist[i] = Integer.MAX_VALUE;
}
visited = new boolean[n + 1];
PriorityQueue<vertex> pq = new PriorityQueue<vertex>();
pq.add(new vertex(1, 0));
while(!pq.isEmpty()) {
vertex top = pq.poll();
if(top.weight > dist[top.v]){
continue;
}
visited[top.v] = true;
dist[top.v] = top.weight;
for(int i = 1; i <= n ; i++) {
if(i != top.v && map[top.v][i] > 0 && !visited[i])
pq.add(new vertex(i, map[top.v][i]));
}
}
long sum = 0;
for(int i = 1 ; i <= n ; i++) {
sum += dist[i];
}
System.out.println(sum);
}
}
이 문제는 최소 스패닝 트리를 구현하는 문제였고 크루스칼 알고리즘(Kruskal)을 사용한다.
● 크루스칼 알고리즘 이란?
Greedy method(탐욕적인 방법) 를 이용하여 가중치를 간선에 할당한 그래프의 모든 정점을 최소 비용으로 연결하는 최적의 해답을 구하는 방식이다.
알고리즘 순서는 다음과 같다.
- 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
- 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않은 간선을 선택한다.
- 해당 간선을 현재의 최소 비용 신장 트리의 집합에 추가한다.
사실 알고리즘 순서만 봐서는 이해가 잘 안간다.
Union-Find 알고리즘을 이용해서 문제를 풀 수 있다.
Union-Find 알고리즘을 통해서 해당 트리가 사이클이 아니라면 가중치의 값을 더해준다.
오름차순 정렬을 했기 때문에 최소인지는 확인 안해도 된다.
예시를 통해 순서를 표현하자면
초기상태
| 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 2 | 3 | 4 | 5 | 6 |
result = 0;
반복문 첫번째,
a = 2, b = 3, weight = 2 가 되고 a 와 b의 parent 는 각각 자기자신이므로 사이클이 아니라 가중치를 더해줄 수 있다.
| 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 3 | 3 | 4 | 5 | 6 |
result = 2
반복문 두번째,
a = 4, b= 5, weight = 3 이 되고, a 와 b의 parent는 각각 자기자신이므로 사이클이 아니라 가중치를 더해줄 수 있다.
| 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 3 | 3 | 4 | 5 | 6 |
result = 5
반복문 세번째,
a = 1, b = 3, weight = 4 이 되고, parent[a] = 1, parenet[b] = 3 으로 각각자신이므로 사이클이 아니라 가중치를 더해 줄 수 있다.
| 1 | 2 | 3 | 4 | 5 | 6 |
| 3 | 3 | 3 | 5 | 5 | 6 |
result = 9
반복문 네번째,
a = 1, b = 2, weight = 5 이 되고, parent[a] = 3, parenet[b] = 3 으로 사이클이므로 가중치를 더하지 않는다.
| 1 | 2 | 3 | 4 | 5 | 6 |
| 3 | 3 | 3 | 5 | 5 | 6 |
result = 9
반복문 다섯번째,
a = 3, b = 4, weight = 6 이 되고, parent[a] = 3, parent[b] = 5 으로 각각의 최종 부모가 다르므로 사이클이 아니다. 가중치를 더해줄 수 있다.
| 1 | 2 | 3 | 4 | 5 | 6 |
| 3 | 3 | 5 | 5 | 5 | 6 |
result = 15
반복문 여섯번째,
a = 2, b = 4, weight = 7 이 되고, find(a) 과정을 통해 parent[a] = 5 로변경, parent[b] = 5 이므로 사이클이다. 따라서 가중치를 더하지 않는다.
| 1 | 2 | 3 | 4 | 5 | 6 |
| 3 | 5 | 5 | 5 | 5 | 6 |
result = 15
반복문 일곱번째,
a = 4, b = 6, weigth = 8 이고, parent[a] = 5, parent[b] = 6 이므로 사이클이 아니므로 가중치를 더해준다.
| 1 | 2 | 3 | 4 | 5 | 6 |
| 3 | 5 | 5 | 5 | 6 | 6 |
result = 23
반복문 여덟번째,
a = 5, b = 6, weight = 8 이고, parent[a] = 6, parent[b] =6 이므로 사이클이라 가중치를 더하지 않는다.
| 1 | 2 | 3 | 4 | 5 | 6 |
| 3 | 5 | 5 | 5 | 6 | 6 |
result = 23
반복문 아홉번째,
a = 3, b = 5, weight = 11 이고, find(a)과정에 의해 parent[a] = 6, parent[b] =6 이므로 사이클이라 가중치를 더하지 않는다.
| 1 | 2 | 3 | 4 | 5 | 6 |
| 3 | 5 | 5 | 5 | 6 | 6 |
result = 23
따라서 결과는 23이 된다.
<전체코드>
import java.io.*;
import java.util.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static int[] parent;
static class vertex implements Comparable<vertex>{
public int v;
public int u;
public int weight;
public vertex(int u, int v, int weight) {
this.u = u;
this.v = v;
this.weight = weight;
}
@Override
public int compareTo(vertex v1) {
// TODO Auto-generated method stub
return this.weight - v1.weight;
}
}
public static void main(String[] args) throws IOException{
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(bufferedReader.readLine());
int m = Integer.parseInt(bufferedReader.readLine());
parent = new int[n + 1];
for(int i = 1 ; i <= n ; i++) {
parent[i] = i;
}
//우선순위 큐를 이용해서 가중치를 기준으로 오름차순 정렬을 한다.
PriorityQueue<vertex> pq = new PriorityQueue<vertex>();
for(int i = 0 ; i < m ; i++) {
StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
pq.add(new vertex(a, b, w));
}
long result = 0;
while(!pq.isEmpty()) {
vertex top = pq.poll();
int a = find(top.u);
int b = find(top.v);
// a 와 b의 부모가 같다면 사이클이므로 넘어간다.
if(a == b)
continue;
union(a, b);
result += top.weight;
}
System.out.println(result);
}
static int find(int a) {
if( a == parent[a])
return a;
//a의 부모가 자기 자신이 아니라면 부모를 변경시켜준다.
return parent[a] = find(parent[a]);
}
static void union(int a, int b) {
//A의 최종 부모
int aRoot = find(a);
//B의 최종 부모
int bRoot = find(b);
//둘의 최종 부모가 같다면 사이클을 형성하고 있다는 것이므로 넘어간다.
if( aRoot != bRoot) {
parent[aRoot] = b;
}
return;
}
}'알고리즘 공부 > 최단거리 알고리즘' 카테고리의 다른 글
| [프로그래머스] 환승 택시 요금 (0) | 2021.05.25 |
|---|---|
| [프로그래머스] 경주로 건설 (0) | 2021.05.07 |
| 백준 1761 (정점들의 거리) - LCA 풀이 (0) | 2021.03.29 |
| 백준 1238 (파티) / 다익스트라 (0) | 2021.02.03 |
| 백준 1261(알고스팟) / 다익스트라 (0) | 2021.01.30 |