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

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

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

 

어떤 문제인가?

존재하는 정점들 중 한 정점에서 다른 모든 정점으로 가는 거리들을 모두 더한 값을 케빈 베이컨 수라고 한다.

이때, 케빈 베이컨수가 가장 작은 정점의 번호를 출력하면 된다.

 

 

 

접근 방법

먼저 정점 간의 거리를 측정해야 하기 때문에 bfs를 사용하기로 했다.

 

vector<int> graph[5001];
bool visited[101];

그래프를 저장할 벡터와 방문 여부를 저장할 배열을 선언해준다.

 

int n, m;
cin >> n >> m;

while (m--) {
    int a, b;
    cin >> a >> b;
    graph[a].push_back(b);
    graph[b].push_back(a);
}

n과 m을 입력받고 m번만큼 간선이 이어주는 두 정점을 입력받는다.

 

 

int bfs(int start, int end) {
    queue<pair<int, int>> q;

    q.push({start, 0});

    while (!q.empty()) {
        int front = q.front().first;
        int count = q.front().second;
        q.pop();

        if (front == end) {
            return count;
        }
        if (visited[front]) {
            continue;
        }

        visited[front] = true;

        for (auto i: graph[front]) {
            if (!visited[i]) {
                q.push({i, count + 1});
            }
        }
    }
    return 0;
}

bfs함수는 파라미터로 넘겨받은 start에서 end까지 가는 거리를 반환하는 함수이다.

 

큐와 pair를 사용해서 시작 지점을 first에, 거리를 second에 저장한다.

 

front와 count변수에 각각 현재 위치와 이동한 거리를 저장한다.

그리고 큐를 팝 해준다.

 

만약 front가 end와 같다면 start부터 end까지 도달했다는 소리이므로 이동거리 count를 반환해준다.

 

만약 front정점이 방문된 정점이면 넘어간다.

 

그리고 front에 연결된 정점들이 방문되지 않았다면 큐에 정점의 번호와 count + 1(거리 증가)을 추가해준다.

 

int minNum = INT_MAX;
int minIndex = 0;

for (int i = 1; i <= n; i++) {
    int total = 0;

    for (int j = 1; j <= n; j++) {

        if (i == j) {
            continue;
        }

        total += bfs(i, j);

        for (int k = 0; k < 102; k++) {
            visited[k] = false;
        }
    }
    if (total < minNum) {
        minNum = total;
        minIndex = i;
    }
}
cout << minIndex << "\n";

 

이제 최솟값을 비교하기 위한 minNum과 그 정점의 번호를 저장할 minIndex를 선언해준다.

 

이중 반복문을 통해 total 변수에 케빈 베이컨 수를 저장해준다.

visited배열을 모두 false로 바꿔준다.

 

만약 minNum보다 total이 작다면 minNum을 total로 바꾸고 minIndex를 현재의 i값으로 바꿔준다.

 

모든 반복이 끝난 후 minIndex를 출력하면 끝!

 

 

무엇이 어려웠는가?

한 정점에서 다른 한 정점까지의 거리를 구하는 방법은 이미 알고있었다.

그래서 문제를 푸는데 큰 어려움은 없었다.

 

 

전체 코드

https://github.com/farmJun/Algorithm_BOJ_PS/blob/main/DFS%EC%99%80%20BFS/1389.cpp

GitHub - farmJun/Algorithm_BOJ_PS: 백준 알고리즘 문제풀이 기록 레포짓입니다.