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

문제 설명

“케빈 베이컨의 6단계 법칙”은 모든 사람들이 영화 배우인 케빈 베이컨과 최대 6단계의 인연으로 연결될 수 있다는 이론입니다.
이 문제에서는 일련의 영화 목록과 그 영화에 출연한 배우들의 정보를 바탕으로, 각 배우와 케빈 베이컨 간의 연결 정도를 계산해야 합니다.
당신은 주어진 여러 영화와 배우 정보에서 각 배우에 대해 케빈 베이컨까지의 최단 거리를 계산하고,
이 거리가 가장 짧은 배우를 찾아야 합니다.

문제 정의

주어지는 입력은 다음과 같습니다.
– 첫 번째 줄에는 배우의 수 N (1 ≤ N ≤ 100)과 영화의 수 M (1 ≤ M ≤ 1000)이 주어집니다.
– 이후 M개의 줄에 걸쳐 각 영화에 출연한 배우들의 목록이 주어지며, 이는 공백으로 구분되어 있습니다.
각 라인은 한 영화에 출연한 배우들의 이름을 나열합니다.

출력은 케빈 베이컨과 가장 가까운 배우의 번호와 그 거리입니다.

문제 접근 방법

문제를 해결하기 위해 그래프 탐색 알고리즘을 사용할 것입니다.
각 배우를 노드로 하고, 두 배우가 동일한 영화에 출연했다면 이들 사이에 간선을 연결합니다.
이후 BFS (너비 우선 탐색)를 이용하여 케빈 베이컨까지의 최단 경로를 계산합니다.
알고리즘은 다음과 같은 순서로 진행됩니다.

그래프를 생성한다. 각 배우를 정점으로 하고, 그들이 출연한 영화를 통해 연결 관계를 정의한다.
BFS를 이용하여 케빈 베이컨과의 거리를 계산한다.
모든 배우에 대한 거리를 비교하여 최단 거리와 해당 배우를 찾는다.

예시 입력

    5 3
    A B C
    B D
    C D E

예시 출력

1 2

코드 구현

다음은 스위프트로 구현한 알고리즘입니다.
그래프를 만들고, BFS를 통해 각 배우와 케빈 베이컨과의 거리를 측정합니다.

        import Foundation

        func findKevinBaconNumber(N: Int, M: Int, movies: [[String]]) -> (Int, Int) {
            var graph = [String: [String]]()
            var distance = [String: Int]()
            
            // 그래프 구성
            for movie in movies {
                for i in 0.. Int {
                var queue = [start]
                var visited = Set()
                var dist = 0
                
                while !queue.isEmpty {
                    let size = queue.count
                    for _ in 0..

    결론
    
        오늘은 "케빈 베이컨의 6단계 법칙"을 주제로 한 알고리즘 문제를 다루었습니다. 
        문제를 통해 그래프 이론과 BFS를 활용하는 방법을 배웠습니다. 
        이를 통해 코딩테스트를 준비하는 데 도움이 되었기를 바랍니다. 
        더 많은 문제와 해결 과정을 이어갈 예정이니 많은 관심 부탁드립니다.

관련