백준 1389 / 케빈 베이컨의 6단계 법칙

(케빈 베이컨이 나오는 영화들을 많이 봤는데, 그 중 제일 재밌었던 건 일급살인이다.)

BFS 연습문제

인접리스트로 문제를 해결했다

코드

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
int n, m;
vector<vector<int>>arr;
 
int ans[101][101];
int d[101][101];
bool over[101];
int ans2[101];
 
void go(int num) {
 
    queue<pair<int,int>>q;
    q.push(make_pair(num, 0));
 
    while (!q.empty()) {
        int now = q.front().first;
        int len = q.front().second;
        q.pop();
 
        for (int i = 1; i <= n; i++) {
            if (num != i) {
                if (now == i && over[now]==false) {
                    ans[num][i] = len;
                    over[now] = true;
                    break;
                }
            }
        }
 
        int c = arr[now].size();
        for (int i = 0; i < c; i++) {
 
            if (d[now][arr[now][i]] == 1) {
                q.push(make_pair(arr[now][i], len + 1));
                d[now][arr[now][i]] = -1;
            }
        }
 
    
 
    }
 
    int sum = 0;
 
    for (int i = 1; i <= n; i++) {
        sum+= ans[num][i];
    }
    ans2[num] = sum;
    //memset(over, false, 101);
    for (int i = 0; i < 101; i++) {
        for (int j = 0; j < 101; j++) {
            if (d[i][j] == -1) {
                d[i][j] = 1;
            }
            ans[i][j] = 0;
            
        }
        over[i] = false;
    }
 
}
 
 
int main() {
 
    //freopen("Text.txt", "r", stdin);
    cin >> n >> m;
 
 
    for (int i = 0; i <= n; i++) {
        vector<int>tmp;
        arr.push_back(tmp);
    }
 
    for (int i = 0; i < m; i++) {
 
        int a, b;
        cin >> a >> b;
        bool jongbok = false;
        
        int c = arr[a].size();
 
        for (int j = 0; j < c; j++) {
            if (arr[a][j] == b) {
                jongbok = true;
            }
        }
        if (jongbok == false) {
 
            arr[a].push_back(b);
            arr[b].push_back(a);
            d[a][b] = 1;
            d[b][a] = 1;
        }
 
 
    }
    for (int i = 1; i <= n; i++) {
        go(i);
    }
 
    int low = 2000000000;
 
    for (int i = 1; i <= n; i++) {
        low = min(ans2[i], low);
    }
 
    for (int i = 1; i <= n; i++) {
        if (ans2[i] == low) {
            cout << i;
            break;
        }
    }
}

역

한 케이스를 수행하고 초기화해주는 걸 잊지말아야한다.

이 문제가 대표적인 플로이드 워셜 알고리즘 문제라는데

플로이드 워셜 알고리즘이 뭔지 알아야겠다.