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

이번 강좌에서는 ‘케빈 베이컨의 6단계 법칙’에 대해 알아보고, 그에 관련된 알고리즘 문제를 해결하는 과정을 살펴보겠습니다. 케빈 베이컨의 6단계 법칙은 모든 사람이 케빈 베이컨과 6단계 이내의 관계를 가진다는 이론입니다. 이를 토대로 그래프 이론을 활용한 문제를 풀어보겠습니다.

문제 설명

주어진 사람들과 그 사람들 간의 관계를 그래프 형태로 나타내고, 특정 인물이 다른 모든 인물들과의 관계를 파악하는 문제입니다. 다음과 같이 문제를 정의합니다:



문제: 케빈 베이컨의 6단계 관계


    
    
  • n명의 사람과 m개의 관계가 주어집니다.
    • 
    
  • 사람들은 1부터 n까지의 정수로 표현됩니다.
    • 
    
  • 각 관계는 두 사람의 ID로 주어지며, 두 사람은 서로 친구입니다.
    • 
    
  • 각 사람의 케빈 베이컨 수를 계산해주세요. 케빈 베이컨 수란, 해당 사람에서 다른 사람까지의 최단 경로의 길이를 의미합니다.
    • 
    
  • 최종적으로, 케빈 베이컨 수가 가장 작은 사람의 ID를 출력합니다. 만약 여러 명이라면 ID가 가장 작은 사람을 선택합니다.
    •

입력 형식

  
ID1 ID2
ID1 ID3
...

출력 형식

케빈 베이컨 수가 가장 작은 사람의 ID

문제 해결 전략

문제 해결을 위해 다음과 같은 절차를 따릅니다:

  1. 입력을 통해 사람과 관계를 그래프 형태로 저장합니다.
  2. 다익스트라(Dijkstra) 알고리즘 또는 BFS(너비 우선 탐색)를 사용하여 각 사람의 케빈 베이컨 수를 계산합니다.
  3. 모든 사람의 케빈 베이컨 수를 비교하여, 가장 작은 수를 가진 사람의 ID를 출력합니다.

코드 구현

이번 문제를 코틀린으로 구현해보겠습니다.


import java.util.*

fun main() {
    val reader = Scanner(System.`in`)
    val n = reader.nextInt() // 사람의 수
    val m = reader.nextInt() // 관계의 수

    // 인접 리스트 초기화
    val graph = Array(n + 1) { mutableListOf() }

    // 관계 입력받기
    for (i in 0 until m) {
        val u = reader.nextInt()
        val v = reader.nextInt()
        graph[u].add(v)
        graph[v].add(u)
    }

    // 각 사람의 케빈 베이컨 수를 저장할 배열
    val kevinBaconScores = IntArray(n + 1)

    // BFS 메소드 정의
    fun bfs(start: Int) {
        val queue: Queue> = LinkedList()
        val visited = BooleanArray(n + 1)
        queue.add(Pair(start, 0)) // 처음 사람과 거리 0
        visited[start] = true

        while (queue.isNotEmpty()) {
            val (current, distance) = queue.poll()
            for (neighbor in graph[current]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true
                    queue.add(Pair(neighbor, distance + 1))
                    kevinBaconScores[start] += distance + 1 // 케빈 베이컨 점수 계산
                }
            }
        }
    }

    // 모든 사람에 대해 BFS 수행
    for (i in 1..n) {
        bfs(i)
    }

    // 최소 케빈 베이컨 수를 가진 사람 찾기
    var minScore = Int.MAX_VALUE
    var resultId = -1
    
    for (i in 1..n) {
        if (kevinBaconScores[i] < minScore) {
            minScore = kevinBaconScores[i]
            resultId = i
        }
    }

    // 결과 출력
    println(resultId)
}

과정 설명

우선, 그래프를 생성하는 과정에서 사람의 수(n)와 관계의 수(m)를 입력받아 인접 리스트 형태로 관계를 저장합니다. 이후 BFS 알고리즘을 사용하여 각 사람의 케빈 베이컨 수를 계산합니다. BFS는 각 사람으로부터 시작해 연결된 모든 사람을 탐색하면서 거리를 증가시켜가며 최종적으로 각 사람의 케빈 베이컨 점수를 기록합니다.

마지막으로, 모든 사람의 케빈 베이컨 점수를 비교하여 가장 작은 값을 찾습니다. 이때, 점수가 동일한 경우에는 ID값이 더 작은 사람을 선택합니다.

결론

이번 강좌를 통해 케빈 베이컨의 6단계 법칙을 활용한 알고리즘 문제를 해결하는 방법을 익혔습니다. 그래프 이론, BFS 알고리즘의 이해는 취업용 알고리즘 시험에서 매우 유용합니다. 이러한 문제를 많이 연습하여 효과적으로 코딩 테스트를 준비하시기 바랍니다.