/<> 백준 1389번 : 케빈 베이컨의 6단계 법칙 (C언어)

https://www.acmicpc.net/problem/1389

 

 

플로이드-워셜(Floyd-Warshall) 알고리즘을 통해 우회하여 연결되어 있는 지를 확인하면 됩니다. 연결되어 있음을 저장하는 배열을 따로 만들 때, 플로이드 워셜 알고리즘을 사용하면서 초기화에 주의하면 됩니다.

 

 

1. 관계 배열을 입력받고, 베이컨 수를 저장하는 배열을 생성합니다.

 

2. 플로이드-워셜 알고리즘을 통해 베이컨 수를 업데이트합니다. 이 때 배열을 초기화하고 진행합니다.

 

3. 베이컨 수가 가장 작은 사람을(노드 번호) 출력합니다.

 

 

<코드>

#include <stdio.h>
#include <stdlib.h>

#define INF 1000000

int n, m;
int relation[101][101] = {0,};
int bridge[101][101] = {0,};

void floyd_warshall() {
    // 베이컨 배열 초기화
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(i == j) {
                bridge[i][j] = 0;
            }
            else if(relation[i][j]) {
                bridge[i][j] = 1;
            }
            else {
                bridge[i][j] = INF;
            }
        }
    }

    // 플로이드 워셜
    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(bridge[i][j] > bridge[i][k] + bridge[k][j]) {
                    bridge[i][j] = bridge[i][k] + bridge[k][j];
                }
            }
        }
    }
}

void print_min() {
    int min_index = 0;
    int min = INF;
    for(int i = 1; i <= n; i++) {
		int kevin = 0;
        for(int j = 1; j <= n; j++) {
            kevin += bridge[i][j];
        }

        if(min > kevin) {
            min = kevin;
            min_index = i;
        }
    }

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

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

    floyd_warshall();
    print_min();

    return 0;
}

 

 

처음 풀 때 베이컨 배열을 초기화하지 않아서 답이 제대로 나오지 않았습니다. 배열을 생성할 때 모두 0으로 정의했으므로, 초기화에 주의해야겠습니다.