[BOJ] 1389: 케빈 베이컨의 6단계 법칙 (C++)

입력

• BOJ 유저의 수
• 친구 관계

---

출력

케빈 베이컨의 수가 가장 작은 사람, 중복이 있는 경우 번호가 가장 작은 사람 출력

• 케빈 베이컨 수 = 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합

---

예제

5 5
1 3
1 4
2 3
3 4
4 5

1: 2(2단계), 3(1단계), 4(1단계), 5(2단계) ⇒ 2 + 1 + 1 + 2 = 6

2: 1(2단계), 3(1단계), 4(2단계), 5(3단계) ⇒ 2 + 1 + 2 + 3 = 8

3: 1(1단계), 2(1단계), 4(1단계), 5(2단계) ⇒ 1 + 1 + 1 + 2 = 5

4: 1(1단계), 2(2단계), 3(1단계), 5(1단계) ⇒ 1 + 2 + 1 + 1 = 5

5: 1(2단계), 2(3단계), 3(2단계), 4(1단계) ⇒ 2 + 3 + 2 + 1 = 8

⇒ 3,4가 5로 케빈 베이컨 수가 가장 작으며, 3이 번호가 더 작으므로 3 출력

---

풀이과정

1. 그래프로 구현

BFS로 각 정점을 시작으로 잡고 다른 정점까지 거리를 계산한다.

정점 A가 시작일 때 A와 B가 연결되어 있고 B와 C가 연결되어 있으면, A와 C 거리는 D[A][B] + 1이다. D[A][C] = D[A][B] + 1이고, D[C][A] = D[B][A] + 1

(구현 중..)

 

2. 플로이드-워셜(Floyd-Warshall) 알고리즘

• 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘(S.S.S.P - Single Source Shortest Path)
• 가중치 그래프에서 모든 정점 간의 최단 경로를 구하는 알고리즘
• 플로이드-워셜(Floyd-Warshall) 알고리즘은 한 번 실행하여 모든 노드 간 최단 경로 계산 가능, 정점과 정점 사이 최단거리 한 번에 계산 가능
• Dynamic Programming 기술로 구현?
• 알고리즘

n = no of vertices
A = matrix of dimension n*n
for k = 1 to n // intermediate vertex
    for i = 1 to n
        for j = 1 to n
            Ak[i, j] = min (Ak-1[i, j], Ak-1[i, k] + Ak-1[k, j])
return A

 

한 정점에서 다른 정점으로 가는 비용을 2차원 배열에 계산

무한	0	1	무한	무한
1	1	0	1	무한
1	무한	1	0	1
무한	무한	무한	1	0

 

노드 1을 거쳐가는 경우 (노드 1이 intermediate vertex인 경우)

무한	0	1	무한	무한
1	1	0	1	무한
1	무한	1	0	1
무한	무한	무한	1	0

min(X에서 Y로 가는 비용, X에서 1로 가는 비용 + 1에서 Y로 가는 비용)

=> D[X][Y] = min(D[X][Y], D[X][1] + D[1][Y])

으로 점화식을 구할 수 있다.

 

노드 2을 거쳐가는 경우

2	0	1	2	3
1	1	0	1	무한
1	2	1	0	1
2	3	무한	1	0

 

노드 3을 거쳐가는 경우

2	0	1	2	3
1	1	0	1	2
1	2	1	0	1
2	3	2	1	0

이렇게 1~5가 중간 노드일 때 각 정점부터 정점까지의 최단경로를 계산하여 업데이트하면 모든 정점에서의 각 정점으로 최단경로가 구해진다.

#include <iostream>
#include <deque>
#include <algorithm>
#include <vector>
#define INF 1000
using namespace std;

int graph[101][101];

void FloydWarshall(int N){

    // k = middle node
    for(int k=1; k<=N; k++){
        // i = source node
        for(int i=1; i<=N; i++){
            // j = destination node
            for(int j=1; j<=N; j++){
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
            }
        }
    }
}

int main(){
    int N, M; // N: 유저 수 (== 정점의 수)(2 <= N <= 100), M: 친구 관계 수(== 간선의 수) (1 <= M <= 5000)
    int answer = INF;
    vector< pair<int,int> > result;
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M;
    
    graph[0][0] = 0;
    
    for(int i=0; i<M; i++){ 
        int A, B; // A, B: 두 친구

        cin >> A >> B;

        graph[A][B] = 1;
        graph[B][A] = 1;
    }

    // i에서 한 번에 도달할 수 없는 경우 INF로 초기화
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            if(i == j) graph[i][j] = 0; // 정점 i와 정점 j가 동일한 경우는 0
            if(j != i && graph[i][j] != 1) graph[i][j] = INF; // 인접하지 않은 경우
        }
    }

    FloydWarshall(N);

    for(int i=1; i<=N; i++){
        int sum=0;
        for(int j=1; j<=N; j++){
            sum += graph[i][j];
        }
        if(sum < answer) { 
            answer = sum;
            result.push_back(make_pair(sum, i));
        }
    }

    sort(result.begin(), result.end());
    cout << result[0].second << endl;
    
    return 0;
}

관계 초기화 방법은, 두 정점이 동일한 경우 0, 두 정점이 인접한 경우 1, 두 정점이 같지 않고 인접하지도 않은 경우 INF를 넣었다.

이후 중간 정점 1~N까지 N x N을 둘러보면서 점화식 D[i][j] = min(D[i][j], D[i][k] + D[k][j])에 따라 값을 업데이트해간다.

graph를 정점과 정점 사이 최단경로에 따라 업데이트한 후, 1일 때 2~N까지 최단경로 합, 2일 때 1, 3~N까지 최단경로 합을 구하고, 만약 최단경로가 마지막으로 업데이트한 최단경로보다 작으면 인덱스와 그 값을 함께 vector에 쌍으로 넣는다.

마지막으로 쌍에서 첫 번째 값이 작은 순서로 sort한 후, result[0].second를 출력하면 최단경로를 가진 인덱스를 구할 수 있다.