[백준][C++] 1389번: 케빈 베이컨의 6단계 법칙 <227>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

1389번: 케빈 베이컨의 6단계 법칙

생각의 흐름

일단 모든 구성원들 자신의 케빈수를 다 구해야 한다는 점에서 플로이드-와샬 방식을 선택하였다.

 

크게 어려운 부분은 없는데, 생각 못한 부분이 있어 이를 적어본다.

if (MAP[i][k] != 0 && MAP[k][j] != 0) {
    if (MAP[i][j] == 0) {
        MAP[i][j] = MAP[i][k] + MAP[k][j];
    } else {
        MAP[i][j] = min(MAP[i][j], MAP[i][k] + MAP[k][j]);
    }
}

MAP[i][j]가 0인 경우도 있을 수 있다.

한번에 연결은 안되있어도, 건너 건너 연결된 케이스이다.

나는 처음에 이부분을 까먹고 적용하지 않아 답이 나오지 않았었다.

 

위 2가지 case만 잘 구분해주면 된다.

 

나의 코드

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define MAX 101
#define INF 987654321

int N, M;
int MAP[MAX][MAX];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        MAP[a][b] = 1;
        MAP[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 (i == j) continue;
                if (MAP[i][k] != 0 && MAP[k][j] != 0) {
                    if (MAP[i][j] == 0) {
                        MAP[i][j] = MAP[i][k] + MAP[k][j];
                    } else {
                        MAP[i][j] = min(MAP[i][j], MAP[i][k] + MAP[k][j]);
                    }
                }
            }
        }
    }

    int ans = INF;
    int person = -1;
    for (int i = 1; i <= N; i++) {
        int sum = 0;
        for (int j = 1; j <= N; j++) {
            sum += MAP[i][j];
        }
        if (ans > sum) {
            person = i;
            ans = sum;
        }
    }
    cout << person;

    return 0;
}