C++ 코딩테스트 강좌, 케빈 베이컨의 6단계 법칙

2023년 10월 3일

작성자: AI 작성

서론

케빈 베이컨의 6단계 법칙은 모든 사람은 케빈 베이컨과 최대 6단계의 간격으로 연결되어 있다는 이론입니다. 이는 사회적 네트워크에서의 관계를 설명하는 흥미로운 개념으로, 여러 분야에서 사랑받는 주제입니다. 오늘 이 글에서는 이 법칙을 알고리즘 문제로 변형하여, C++을 사용한 문제 풀이 과정을 자세히 설명하겠습니다.

우리가 풀어볼 문제는 “케빈 베이컨을 가장 빨리 찾는 사람” 문제입니다. 연구를 통해 여러 명의 사람 간의 친구 관계가 주어질 때, 각 사람에 대한 케빈 베이컨의 연결 정도를 계산하는 것입니다.

문제 정의

주어진 네트워크에서 각 사람의 케빈 베이컨 숫자를 계산하고, 가장 숫자가 낮은 사람을 찾는 문제입니다. 이를 위해 입력으로 사람 수와 그들 간의 친구 관계를 설정해야 합니다.

문제 설명

입력으로는 다음과 같은 형식이 주어집니다:

첫 번째 줄에 사람의 수 N (1 ≤ N ≤ 100)
두 번째 줄부터 각 줄에 친구 관계를 나타내는 두 정수 A, B (A와 B는 서로 친구)]

출력으로는 케빈 베이컨과 가장 가까운 사람의 번호를 출력해야 합니다. 만약 여러 명이라면 가장 작은 번호를 출력합니다.

문제 해결 접근법

이 문제를 해결하기 위해 그래프 탐색 기법을 사용할 것입니다. 사람을 정점(Vertex)으로, 친구 관계를 간선(Edge)으로 보고 BFS(너비 우선 탐색)를 적용합니다. 각 사람으로부터 케빈 베이컨까지의 최단 거리를 계산하고, 그 중 최소값을 찾겠습니다.

알고리즘

입력을 바탕으로 그래프를 인접 리스트로 구성합니다.
BFS를 통해 각 사람의 케빈 베이컨 숫자를 계산합니다.
계산한 케빈 베이컨 숫자를 비교하여 최소값을 찾습니다.

C++ 구현

이제 위의 알고리즘을 기반으로 C++ 코드를 구현해보겠습니다.


#include <iostream>
#include <vector>
#include <queue>
#include <limits> 
using namespace std;

int main() {
    int N, M;
    cin >> N >> M; // 사람 수 N, 친구 관계 수 M
    vector<vector<int>> graph(N + 1); // 인접 리스트

    for (int i = 0; i < M; i++) {
        int A, B;
        cin >> A >> B; // 친구 관계 A, B
        graph[A].push_back(B);
        graph[B].push_back(A); // 양방향 그래프
    }

    int min_bacon = numeric_limits<int>::max();
    int answer = 0;

    for (int i = 1; i <= N; i++) {
        vector<int> distance(N + 1, -1); // 각 사람의 거리 초기화
        queue<int> q;
        distance[i] = 0; // 자신으로부터 0 거리
        q.push(i); // 큐에 자신 추가

        while (!q.empty()) {
            int current = q.front();
            q.pop();
            for (int neighbor : graph[current]) {
                if (distance[neighbor] == -1) {
                    distance[neighbor] = distance[current] + 1; // 거리 계산
                    q.push(neighbor); // 탐색할 친구 추가
                }
            }
        }

        int bacon_count = 0;
        for (int d : distance) {
            if (d != -1) {
                bacon_count += d; // 케빈 베이컨 숫자 합산
            }
        }

        if (bacon_count < min_bacon) {
            min_bacon = bacon_count; // 최소값 업데이트
            answer = i; // 사람 번호 기록
        }
    }

    cout << answer << endl; // 결과 출력
    return 0;
}

코드 설명

위의 C++ 코드는 다음과 같은 주요 단계를 포함합니다:

입력 처리: N과 M을 입력받고, 친구 관계를 인접 리스트 형태로 저장합니다.
BFS 구현: 각 사람에 대해 BFS를 수행하여 거리를 계산합니다.
결과 계산: 계산된 거리를 바탕으로 케빈 베이컨 숫자를 갱신하고, 최종적으로 최솟값을 찾습니다.

Complexity Analysis

이 알고리즘의 시간 복잡도는 O(N + M)입니다. 각 사람이 BFS로 탐색을 하며, 각 간선을 한 번만 탐색하기 때문입니다. 이는 주어진 문제의 입력 범위 내에서 충분히 효율적입니다.

결론

이번 강좌에서는 케빈 베이컨의 6단계 법칙을 활용한 알고리즘 문제를 C++으로 해결하는 방법을 살펴보았습니다. BFS를 활용한 그래프 탐색 기법을 통해 네트워크 내의 관계를 분석할 수 있었습니다. 이러한 유형의 문제는 코딩 테스트에서 자주 출제되므로, 다양한 문제를 푸는 연습을 통해 숙련도를 높이는 것이 중요합니다.

마지막으로, 이 문제 해결 과정을 통해 코딩 테스트 대비뿐만 아니라, 실제 프로그래밍에서 발생할 수 있는 다양한 문제들을 보다 체계적으로 해결하는 데 도움을 줄 수 있을 것입니다.

서론