[백준] 1389 케빈 베이컨의 6단계 법칙

Posted on | In

이 문제를 어젠가 처음 접했는데 뭔가 내가 계속 걸리던 부분을 콕? 집어서 처참히 무너졌다. 그래서 꼼꼼히 봐야 하는데 계속 미루게 되고 막 대충 보고 싶고 그렇다. 이렇게 블로그에 올리지도 않으면 진짜 그냥 대충 보고 끝날 거 같아서 이것만 써 놓고 자려고 한다. 나는 2178_미로탐색 문제처럼 dfs로 흝으면서 각 경우의 최소 경로를 구해서 더하고 출력하는 줄 알았다. 근데 나 자체가 이런 미로 탐색 문제를 이해를 제대로 못했는지 코드를 짜는데 계속 뭔가 어긋났다. 그래서 계속 코드를 쓰지도 못하고 그만두지도 못하는 어영부영한 상태가 되어서 과감하게 풀이를 보기로 했다! 이 풀이를 참고했다. 감사합니다 ->풀이

문제 설명

문제는 그냥 두 노드 간에 얼마나 떨어져 있는지(최소 경로)를 구할 수 있으면 거의 다 푼 문제라고 생각하면 된다. 최소 경로를 저장하고 있는 행렬이 있다면 거기서 n번 노드가 자기 자신을 제외한 모든 노드들 사이의 경로의 합을 구할 수 있고, 이 경로의 합이 최소인 노드의 번호를 출력하면 되는 문제이다. 결국 두 노드 간의 거리를 어떻게 구하느냐가 관건인 문제이다.

문제 풀이

나는 그래서 미로 탐색 문제처럼 dfs로 흝으면서 최솟값을 구하면 되는 거라고 생각했는데, 생각보다 이 최솟값을 배열에 저장하는 과정이 순조롭지 않았다. depth를 return 하도록 한 함수에서 depth를 바꾸지 않고 배열에 저장하는 게 힘들어서(무슨 소리인지 이해할 필요는 없다) 과감하게 써놓은 코드를 다 지우고 답지를 보았다. 이거는 플로이드 와샬 알고리즘 이라고 한다. 알고리즘 자체는 그리 복잡하지 않은 것 같다. adj[n][n] 행렬이 있을 때 1,1 부터 채우기 시작하고, adj[i][j]위치의 값보다 adj[i][k]+adj[k][j]가 작을 때 adj[i][j]를 갱신한다. 그러니까 adj[i][j]가 의미하는 값은 i에서 j로 갈때의 최단 경로라서, adj[i][k]+adj[k][j]의 의미는 i에서 k까지, 그리고 계속 k에서 j까지가는, 즉 i에서 j로 가는 경로 중 k를 거치는 경로를 의미한다. 모든 k에 대해서 흝으므로 adj[i][j]는 최단 경로의 길이를 가질 수밖에 없다. 뭔가 다익스트라 알고리즘? 같다는 아주 짧은 식견이지만 생각이 들기도 하는 것 같다.

1
2
3
4
5
6
7
8
9
for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(adj[i][k]+adj[k][j]<adj[i][j]){
                    adj[i][j]=adj[i][k]+adj[k][j];
                }
            }
        }
    }

코드는 다음과 같다.

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
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstdio>
#include <vector>
using namespace std;

int n, m;
int adj[101][101];

int main(){
    int a, b;
    scanf("%d%d", &n, &m);
    for(int i=0;i<m;i++){
        scanf("%d%d", &a, &b);
        adj[a][b]=1;
        adj[b][a]=1;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i != j && adj[i][j] != 1) {
                adj[i][j] = 10000000;
            }
        }
    }

    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(adj[i][k]+adj[k][j]<adj[i][j]){
                    adj[i][j]=adj[i][k]+adj[k][j];
                }
            }
        }
    }

    int max=10000000;
    int person=0;
    for(int i=1;i<=n;i++){
        int sum=0;
        for(int j=1;j<=n;j++){
            sum+=adj[i][j];
        }
        if(sum<max) {
            max=sum;
            person=i;
        }
    }

    printf("%d\n", person);
}

BFS

이 문제를 bfs로도 풀 수 있다고 하길래, 약간 의아했었다. 난 dfs로 계속 따져 주어야 한다고 생각했는데 그게 아니라 bfs로 한 걸음씩? 나아가는 거였다. bfs로 풀면 된다는 걸 알고 난 후에 풀이를 작성하는 것은 별로 어렵지는 않았다. bfs를 시작하는 노드가 두 노드간의 거리 중에 한 노드가 된다. 따라서 1번 노드를 기준으로 bfs를 수행하면서 path[i] 배열에 시작 노드와 i 노드 사이의 거리를 저장해 주면 된다. 이때 시작 노드와 i 노드 사이의 거리는 시작 노드와 i의 부모 노드 사이의 거리에서 한걸음만 더 가면 되므로 1을 더해주면서 bfs를 수행하면 된다. 이렇게 bfs를 모두 수행하고 나면 path에 s 노드를 시작 노드로 잡았을 때 각 노드와 떨어진 거리가 저장이 되게 된다. 이걸 for문을 통해 더한 걸 나는 bfs의 return 값이 되게 했다. 따라서 이 bfs의 return 값이 가장 작은 노드가 내가 맞춰야 할 답이 된다.

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <queue>
#include <string.h>
using namespace std;

int n, m;
int adj[101][101]={0,};
int path[101]={0, };
bool v[101];

int bfs(int s){
    queue<int> q;
    q.push(s);

    memset(path, 0, sizeof(path));
    memset(v, false, sizeof(v));

    while(!q.empty()){
        int x=q.front();
        v[x]=true;
        q.pop();
        for(int i=1;i<=101;i++){
            if(adj[x][i]==1 && !v[i]){
                q.push(i);
                v[i]=true;
                path[i]=path[x]+1;
            }
        }
    }

    int sum=0;
    for(int i=1;i<=n;i++) sum+=path[i];
    return sum;
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i=0;i<m;i++){
        int a, b;
        scanf("%d%d", &a, &b);
        adj[a][b]=1;
        adj[b][a]=1;
    }
    
    int max=10000;
    int argmax=0;
    for(int i=1;i<=n;i++){
        int c=bfs(i);
        if(max>c) {
            max=c;
            argmax=i;
        }
    }
    printf("%d\n", argmax);
}