10159번: 저울 
문제 링크: 10159번: 저울
개요
어떤 정점에서 다른 정점으로 가는 최단경로를 알고 싶을 때 사용하는 알고리즘은 대표적으로 다익스트라(Dijkstra) 알고리즘과 플로이드 와샬(Floyd–Warshall) 알고리즘이 있다. 플로이드 와샬 알고리즘은 3중 반복문을 사용하기 때문에 우선순위 큐를 사용하지 않는 다익스트라 알고리즘의 시간복잡도(O(n²))보다도 더 큰 시간복잡도(O(n³))를 갖는다. 하지만 한 정점에서부터의 최단경로를 알게 되는 다익스트라 알고리즘과는 달리 모든 정점에서 모든 정점으로의 최단 경로를 알 수 있다는 장점이 있다. 이 문제에서는 모든 정점에 대해 최단 경로를 알 수 있는 정점 개수를 각각 출력해야 하기 떄문에 플로이드 와샬 알고리즘이 적합하다.
플로이드 와샬
2차원 배열 dist[i][j]는 i에서 j로 가는 최단 경로를 저장하는 것이 아니라, i가 j보다 무거우면 1, 가벼우면 -1, 알 수 없으면 0을 저장했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for (int i = 0; i < m; i++) {
int a, b;
scanf("%d %d", &a, &b);
dist[a][b] = 1, dist[b][a] = -1;
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist[i][k] && dist[i][k] == dist[k][j]) {
dist[i][j] = dist[i][k];
}
}
}
}
k를 거쳐서 i와 j를 비교할 때, w(i) < w(k) < w(j) 이거나 w(i) > w(k) > w(j) 이어야만 w(i)와 w(j)의 대소관계를 알 수 있다. 따라서 dist[i][k]와 dist[k][j]가 같은 경우에만 dist[i][j]를 갱신해주었다. (w(n) = n의 무게)
전체 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h>
#include <string.h>
#pragma warning(disable:4996)
#pragma warning(disable:6031)
#define MAX_N 100
int main() {
int n, m, dist[MAX_N+1][MAX_N+1] = { 0 };
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) {
int a, b;
scanf("%d %d", &a, &b);
dist[a][b] = 1, dist[b][a] = -1;
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist[i][k] && dist[i][k] == dist[k][j]) {
dist[i][j] = dist[i][k];
}
}
}
}
for (int i = 1; i <= n; i++) {
int crCnt = 0;
for (int j = 1; j <= n; j++) {
if (!dist[i][j]) crCnt++;
}
printf("%d\n", crCnt - 1);
}
return 0;
}