백준[1389] - 케빈 베이컨의 6단계 법칙

문제

백준 1389 문제 보기

접근 방법

유저의 숫자가 주어진다면 각 유저들간 친구 관계를 파악하기 위해 모든 유저를 상대로 dfs 탐색을 진행한다.

• 유저 1과 나머지 유저들 간의 친구 관계를 계산하기 위해 유저 1 대상으로 연결 요소를 완전 탐색하고 거리차를 증가한다.
• 각 친구들까지의 거리차를 cnt 배열에 따로 저장한다.
• 탐색이 완료되면 총 거리를 계산한다.
• cnt 배열을 초기화하고 다음 유저에 대해서 위의 과정을 반복한다.

코드

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

int N, M, person = 101, ans = 987654321;
int cnt[101];
vector<vector<int>> relation(101);

// diff: 지정된 친구로부터 거리차, num: 친구 번호
void dfs(int diff, int num) {
    // cnt[num]에 거리차를 저장
    if(cnt[num] != 0) {
        cnt[num] = min(diff, cnt[num]);
    } else {
        cnt[num] = diff;
    }

    // 연결된 친구 모두 탐색
    for(int j = 0; j < relation[num].size(); j ++) {
        int next = relation[num][j];
        // 친구를 포함하지 않았거나 더 가까운 사이의 친구라면 탐색
        if(cnt[next] == 0 || cnt[next] > diff + 1 ) {
            dfs(diff + 1, next);
        }
    }
}

int main() {
    cin >> N >> M;
    for(int i = 0; i < M; i ++) {
        int from, to;
        cin >> from >> to;
        // 양방향 저장
        relation[from].push_back(to);
        relation[to].push_back(from);
    }

    for(int i = 1; i <= N; i ++) {
        // 친구들과의 거리차 초기화
        memset(cnt, 0, sizeof(cnt));
        for(int j = 0; j < relation[i].size(); j ++) {
            dfs(1, relation[i][j]);
        }

        int temp = 0;
        for(int j = 1; j <= N; j ++) {
            if(j == i) {
                continue;
            }
            temp += cnt[j];
        }
        // 최소인지 검사
        if(ans > temp) {
            ans = temp;
            person = i;
        }
        else if(ans == temp) {
            person = min(person, i);
        }
    }

    cout << person;
    return 0;
}