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

이번 글에서는 매우 흥미로운 개념인 “케빈 베이컨의 6단계 법칙”에 대해 알아보겠습니다. 이 법칙은 모든 사람이 6단계 이내에 케빈 베이컨과 연결될 수 있다는 이론입니다. 영화 산업에서 자주 인용되며, 사회적 네트워킹 이론에서도 중요한 역할을 합니다. 우리는 이 개념을 바탕으로 알고리즘 문제를 풀어보겠습니다.

문제 설명

다음과 같은 조건의 알고리즘 문제를 다룹니다:

문제 제목: 케빈 베이컨의 친구 찾기

문제 설명: N명의 배우가 있고, 각 배우는 다른 배우와 친구일 수 있습니다. 주어진 N명의 배우와 그들의 친구 관계가 있을 때, 각 배우와 케빈 베이컨 간의 관계의 최소 단계(최소 친구의 수)가 몇 단계인지 계산하는 문제입니다. 이러한 관계는 비행기로 비유할 수 있으며, 관계의 간선은 서로가 친구임을 의미합니다.

한 배우 A와 다른 배우 B의 친구 관계가 주어진다면, 두 배우는 1단계 관계에 있습니다. A와 B의 친구 C가 있다면, A와 C는 2단계 관계에 있습니다. 이와 같이 진행하여, 모든 배우들과 케빈 베이컨 간의 최소 친구 관계를 계산해야 합니다.

입력 형식

  • 첫 번째 줄에 자연수 N (1 ≤ N ≤ 100)과 M (0 ≤ M ≤ 10,000)이 주어집니다.
  • 두 번째 줄 부터 M줄에 걸쳐서 두 배우의 친구 관계가 주어집니다. 예를 들어 “1 2″는 1번 배우와 2번 배우가 서로 친구임을 의미합니다.

출력 형식

각 배우에 대해 케빈 베이컨과의 최소 관계의 단계를 출력합니다. 만약 케빈 베이컨과 관계가 없다면 -1을 출력해야 합니다.

입력 예시

5 4
1 2
1 3
2 4
3 5

출력 예시

2
3
3

문제 풀이 접근 방식

이 문제를 해결하기 위해서는 그래프 탐색 알고리즘을 사용할 수 있습니다. 친구 관계를 그래프로 구성하고, 각 배우에서 케빈 베이컨까지의 최단 경로를 찾는 방식입니다. 이를 위해 다음과 같은 단계를 따릅니다:

  1. 그래프 구성: 주어진 친구 관계를 인접 리스트 방식으로 그래프를 구성합니다.
  2. BFS (너비 우선 탐색): 모든 배우에 대해 BFS를 수행하여 케빈 베이컨까지의 최단 경로를 찾습니다.
  3. 출력: 각 배우와 케빈 베이컨의 최소 관계 단계를 계산하여 출력합니다.

코드 구현

이제 위의 접근 방식을 C#으로 구현해보겠습니다.


using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        int N, M;
        string[] firstLine = Console.ReadLine().Split();
        N = int.Parse(firstLine[0]);
        M = int.Parse(firstLine[1]);

        List[] graph = new List[N + 1];
        for (int i = 1; i <= N; i++)
        {
            graph[i] = new List();
        }

        for (int i = 0; i < M; i++)
        {
            string[] edge = Console.ReadLine().Split();
            int u = int.Parse(edge[0]);
            int v = int.Parse(edge[1]);
            graph[u].Add(v);
            graph[v].Add(u); // 친구 관계는 양방향입니다.
        }

        int[] distances = new int[N + 1];

        for (int i = 1; i <= N; i++)
        {
            BFS(graph, distances, i);
        }

        for (int i = 1; i < distances.Length; i++)
        {
            Console.WriteLine(distances[i] == 0 ? -1 : distances[i]);
        }
    }

    static void BFS(List[] graph, int[] distances, int start)
    {
        Queue queue = new Queue();
        bool[] visited = new bool[graph.Length];
        int[] localDistances = new int[graph.Length];
        
        queue.Enqueue(start);
        visited[start] = true;

        while (queue.Count > 0)
        {
            int node = queue.Dequeue();

            foreach (var neighbor in graph[node])
            {
                if (!visited[neighbor])
                {
                    visited[neighbor] = true;
                    queue.Enqueue(neighbor);
                    localDistances[neighbor] = localDistances[node] + 1;
                }
            }
        }

        for (int j = 1; j < distances.Length; j++)
        {
            if (distances[j] == 0 && localDistances[j] > 0)
            {
                distances[j] = localDistances[j];
            }
        }
    }
}

해설

이 코드에서는 먼저 배우의 수와 친구 관계의 수를 입력받고, 친구 관계를 기반으로 그래프를 구성합니다. 이후 각 배우에 대해 BFS를 수행하여 케빈 베이컨까지의 거리를 계산합니다. BFS는 큐를 활용하여 현재 노드와 연결된 모든 노드를 탐색하고, 최단 거리 계산에 매우 적합한 알고리즘입니다.

각 배우 별로 BFS 결과를 통해 최소 친구 관계 단계를 출력합니다. 만약 케빈 베이컨과 연결되지 않았다면, -1을 출력하도록 설정했습니다.

최적화 및 추가 사항

정확한 결과를 얻기 위해 몇 가지 최적화를 고려할 수 있습니다:

  • 친구 관계가 없는 경우를 고려하여 초기 거리 배열을 설정할 때, 모든 요소를 -1로 초기화할 수 있습니다.
  • BFS를 통해 탐색할 때, 중복 노드를 제거하여 메모리를 절약할 수 있습니다.

결론

이번 강좌에서는 케빈 베이컨의 6단계 법칙을 기반으로 알고리즘 문제를 풀어보았습니다. 그래프 탐색 알고리즘의 중요성과 BFS의 활용을 통해 여러 문제를 해결할 수 있는 능력을 키우시길 바랍니다. 문제를 풀면서 직면한 어려움을 해결하고, 다양한 해법을 시도해보는 것이 알고리즘 실력을 향상시키는 데 큰 도움이 됩니다.

앞으로도 다양한 알고리즘 문제를 다루며, 이론과 실전 코딩이 결합된 교육 콘텐츠를 제공할 예정입니다. 많은 관심과 응원 부탁드립니다.

© 2023 알고리즘 강좌. 모든 권리 보유.