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

1389 케빈 베이컨의 6단계 법칙

문제로 이동

문제 요약

사람들의 관계에서 케빈 베이컨의 수를 찾고, 케빈 베이컨 수가 가장 작은 사람을 찾아야한다.

알고리즘

1. 친구 관계를 양방향 그래프로 입력받는다.
2. 노드 간 depth를 계산하여 케빈 베이컨의 수를 계산한다.
3. 케빈 베이컨의 수가 가장 작은 사람을 찾아 출력한다.

접근 방법

• 친구 관계를 양방향 그래프로 입력받아야 하는 이유
  • A와 B가 친구라면, B와 A도 친구이기 때문이다.
  • 그래프를 쉽게 입력받기 위해서 모든 노드에 대해 빈 배열을 선언해주면 contains연산 없이 삽입할 수 있다!
• 케빈 베이컨의 수 계산하는 방법
  • 케빈 베이컨의 수를 다시 생각해보면, 노드 간 depth를 계산하면 되는 것이다.
  • 즉, 1-3-2라는 관계가 있을 때, 1과 2사이의 depth는 2이고, 케빈 베이컨의 수 역시 2가 된다는 것이다.
  • (가까운 노드먼저 모두 방문해야하므로, BFS를 이용해야한다.)
  • 이를 구현하기 위해 visited 배열을 활용하여 각 Depth를 계산할 수 있다.
• 케빈 베이컨의 수가 가장 적은 사람, 번호가 가장 작은 사람을 출력하는 방법
  • bfs의 결과를 저장해놓고 그 결과보다 작은 경우! 업데이트 시켜주면 된다.
  • 작거나 같은 경우를 판별하지 않으면 된다. (Array로 순차적으로 호출하기 때문에, 가장 번호가 출력될 수밖에 없다)

코드

let input = readLine()!.split { $0 == " " }.map { Int($0)! }, (n, m) = (input[0], input[1])
var graph = [Int: [Int]]()
var count = Int.max
var result = -1
Array(1...n).forEach { graph[$0] = [] }

// 1. 친구 관계를 양방향 간선으로 입력받는다.
for _ in 0 ..< m {
    let input = readLine()!.split { $0 == " " }.map { Int($0)! }
    let a = input[0], b = input[1]
    graph[a]!.append(b)
    graph[b]!.append(a)
}

// 3. 케빈 베이컨의 수가 가장 작은 사람을 찾아 출력한다.
Array(1...n).forEach {
    let kebin = bfs($0)
    if count > kebin {
        count = kebin
        result = $0
    }
}
print(result)


// 2. 케빈 베이컨의 수를 계산한다.
func bfs(_ node: Int) -> Int {
    var visited = [Int](repeating: -1, count: n+1)
    var queue = [node]
    visited[node] = 0
    var result = 0
    while !queue.isEmpty {
        let n = queue.removeFirst()
        guard let nodes = graph[n] else { continue }
        for next in nodes {
            if visited[next] == -1 {
                let visitCount = visited[n] + 1
                visited[next] = visitCount
                queue.append(next)
                result += visitCount
            }
        }
    }
    return result
}