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

import Foundation

/// 케빈 베이컨 수 : 모든 사람과 케빈 베이컨 게임을 했을 때 나오는 단계의 합
/// BOJ 유저가 5명이고, 1-3, 1-4, 2-3, 3-4, 4-5가 친구인 경우
/// 1은 친구와 이어지기 위해 1-3-2, 1-3, 1-4, 1-4-5 이런 단계를 거친다. 즉 케빈 베이컨 수는 2 + 1 + 1 + 2 = 6이다.
/// BOJ 유저의 수와 친구관계가 입력으로 주어졌을 때, 케빈 베이컨 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.
/// N : 유저의 수
/// M : 친구관계의 수

let NM = readLine()!.components(separatedBy: " ").map { Int($0)! }
let N = NM[0]
let M = NM[1]

var graph = [String: [String]]()

for i in 1...N {
    graph[String(i)] = []
}

for _ in 1...M {
    let AB = readLine()!.components(separatedBy: " ").map { Int($0)! }
    let A = String(AB[0])
    let B = String(AB[1])
    graph[A]?.append(B)
    graph[B]?.append(A)
}

var kbNumArr = [Int]()
for i in 1...N {
    kbNumArr.append(BFS(n: String(i)))
}

print(kbNumArr.firstIndex(of: kbNumArr.min()!)! + 1)

// n번 유저의 케빈 베이컨 수를 반환
func BFS(n: String) -> Int {
    var visitedQueue: [String] = []
    var needVisitQueue: [String] = [n]
    var tempFloor: Set<String> = [n]    // 현재 층의 노드를 담는 배열
    var currentFloor = 0    // 현재 층
    var cnt = 0
    
    while !needVisitQueue.isEmpty {

        let node: String = needVisitQueue.removeFirst()
        if visitedQueue.contains(node) { continue }
        
        // 방문하지 않은 노드면 아래 함수 실행
        
        /// 현재층 노드를 담는 배열에 노드가 없는 경우
        /// 인접한 배열 중에서
        /// 방문하지 않은 노드만 가져와서 담고 층수를 올려라
        if !tempFloor.contains(node) {
            for currentFloorNode in tempFloor {
                for adjacentNode in graph[currentFloorNode] ?? [] {
                    if !visitedQueue.contains(adjacentNode) {
                        tempFloor.insert(adjacentNode)
                        tempFloor.remove(currentFloorNode)
                    }
                }
            }
            currentFloor += 1
        }
        
        
        visitedQueue.append(node)
        needVisitQueue += graph[node] ?? []

        cnt += currentFloor
    }
    
    return cnt
}

풀었던 아이디어

1. bfs와 관련된 로직은 https://jerry311.tistory.com/38 이쪽에서 다뤘던 방식으로 구현했다.

2. 인접한 노드를 방문할때마다 tempFloor 배열에 현재 층의 노드를 배열로 저장함

0층 - 1

1층 - 3, 4

2층 - 2, 5

 

3. 이런식으로 각층마다 노드를 넣어놓고 다른 값이 들어올때마다 currentFloor를 하나씩 더해줬다.

4. 층수가 결국 거리의 수니까 그걸 더해서 케빈 베이컨 수를 구했다.