백준 1389번 케빈 베이컨의 6단계 법칙 C++ BFS

리뷰

실버 1문제에서 왜 틀렸나.. 고민했는데 부등호 하나 빼먹은게 원인이었다. BFS로 풀긴 했는데 for문을 세번 사용하는 플로이드-워셜로도 풀 수 있다고 한다.

 

문제 풀이

1. n값을 입력 받고 인접리스트를 n + 1 크기로 초기화 해준다.
2. m값을 입력 받고 m줄에 걸쳐 입력되는 두개의 노드를 쌍방향으로 연결 해준다.
3. 각 노드별 케빈 베이컨 숫자를 받아올 벡터 kb를 n + 1 크기로 초기화 해준 후 브루트포스로 bfs를 돌려준다.
4. bfs 내에서 방문 배열을 0으로 초기화, 현재 노드를 방문처리, 다른 노드에 방문 할때마다 ct를 1 올려주고 cnt에 ct를 더해준다. 만약 cnt가 여태까지의 최소 cnt보다 클 경우 바로 return 해줘도 된다.
5. 모든 노드에 대해 bfs가 종료된 후 가장 적은 케빈 베이컨 숫자가 min_val인 노드를 출력하고 break 해준다.

 

참고 사항

인덱싱을 편하게 해주기 위해 n + 1 크기로 초기화 해준 경우 for문 돌릴때 1 ~ n + 1까지의 범위를 탐색하게 해주자

 

 

정답 코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m;
int min_val = 999999999;
vector<vector<int>> f;

struct POS {
    int x, time;
};

int bfs(int now) {
    queue<POS> q;
    q.push({ now, 0 });
    int v[101] = { 0 };
    v[now] = 1;
    int cnt = 0;

    while (!q.empty()) {
        if (cnt > min_val) return cnt;
        POS pos = q.front(); q.pop();
        int cx = pos.x, ct = pos.time;
        for (int i : f[cx]) {
            if (v[i]) continue;
            v[i] = 1;
            cnt += ct + 1;
            q.push({ i, ct + 1 });
        }
    }
    return cnt;
}

int main() {
    cin >> n >> m;
    f.resize(n + 1);

    for (int i = 0; i < m; i++) {
        int n1, n2;
        cin >> n1 >> n2;
        f[n1].push_back(n2);
        f[n2].push_back(n1);
    }

    vector<int> kb(n + 1);

    for (int i = 1; i <= n; i++) {
        kb[i] = bfs(i);
        if (min_val > kb[i]) {
            min_val = kb[i];
        }
    }
    for (int i = 1; i <= n; i++) {
        if (kb[i] == min_val) {
            cout << i;
            break;
        }        
    }
}