[Kotlin, S1] 백준 1389번 케빈 베이컨의 6단계 법칙

출처: unsplash.com

 

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

Silver 1

#그래프 이론 #그래프 탐색 #너비 우선 탐색 #최단 경로 #플로이드–워셜

 

문제 내용

 

 

문제 접근

각 사용자가 어떤 사용자와 관계를 맺고 있는지 확인해서 그래프를 돌면서 몇 번째 단계에서 원하는 사용자에게 닿을 수 있는지 확인해야 한다.

입력 예제 1을 이용해 그래프를 먼저 구성해 주겠다. 그래프의 구성은 다음과 같이 해줄 수 있다.

사진 1-1

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.min

private var graph = arrayOf<MutableList<Int>>()
private var visited = booleanArrayOf()
private var result = 0

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (user, relationships) = readLine().split(" ").map { it.toInt() }
    graph = Array(user + 1) { mutableListOf() }
    visited = BooleanArray(user + 1)

    for (i in 0 until relationships) {
        val relationship = readLine().split(" ").map { it.toInt() }
        graph[relationship[0]].add(relationship[1])
        graph[relationship[1]].add(relationship[0])
    }

    var currentMin = Int.MAX_VALUE
    var answer = 0
    for (i in user downTo 1) {
        var totalRes = 0
        visited.fill(false)
        result = 0

        for (f in 1 .. user) {
            visited.fill(false)
            result = 0

            if (i == f) continue
            find(i, f)

            totalRes += result
        }

        val newMin = min(currentMin, totalRes)

        // 더 적은 케빈 베이컨 수를 구하기.
        if (newMin < currentMin) {
            currentMin = newMin
            answer = i
        }
        // 현재 i의 케빈 베이컨 수의 합과 현제 케빈 베이컨 수의 최솟갑과 같다면 i를 갱신해주기.
        else if (totalRes == currentMin) {
            answer = i
        }
    }

    println(answer)
}

private fun find(user: Int, toFind: Int) {
    val queue: Queue<List<Int>> = LinkedList()
    visited[user] = true

    for (u in graph[user]) {
        if (u == toFind) {
            result = 1
            return
        }
        queue.add(listOf(u, 1))
    }

    while (queue.isNotEmpty()) {
        val data = queue.poll()
        val checkUser = data[0]
        val level = data[1]

        for (g in graph[checkUser]) {
            if (!visited[g]) {
                if (g == toFind) {
                    result += level + 1
                    return
                }
                queue.add(listOf(g, level + 1))
                visited[g] = true
            }
        }
    }
}

예제 입력 1에서 두 번째 줄의 입력이 1 3인데, 그래서 1에 해당하는 위치에는 3을 넣고, 3에 해당하는 위치에는 1을 넣어서 서로 관계를 맺어 준다. 이를 모든 입력값의 관계를 추가해 주면 그래프가 다음과 같이 생성될 것이다.

이제 위 그래프에서 유저 5가 유저 2까지 이동하려면 5 -> 4 -> 3 -> 2로 총 3번의 이동이 있어야 하기 때문에 정답은 3이 된다.

 

이제 코드를 활용해 조건을 탐색해 보자.케빈 베이컨의 수가 가장 적은 수를 구해야 하기 때문에 min() 함수를 사용할 수 있다.또한 케빈 베이컨 수가 같은 경우도 존재할 수 있다. 예제 입력 1의 경우에도 최소가 3, 4로 케빈 베이컨 수는 5로 똑같다.이 경우에는 더 번호가 작은 사람의 번호를 출력한다.이 문제의 답을 구하기 위해서는 기준이 되는 사람과 찾아야 하는 사람 총 2가지가 필요하다. 찾아야 하는 사람은 기준이 되는 사람과 같으면 안 된다.2중 반복문을 사용해서 기준이 되는 사람과 찾아야 하는 사람을 구할 수 있다.두 값이 같은 경우에는 continue로 넘기면 된다.또한 반복 순서를 큰 수에서 작은 수로 가도록 반복해야 한다. 그래야 위에 언급했던 케빈 베이컨 수가 같은 사람이 여러 명일 때 번호가 작은 사람을 구하기 쉽다.bfs를 이용해 문제를 해결한다.

 

자세한 bfs 로직은 문제 풀이에서 적어 보겠다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.min

private var graph = arrayOf<MutableList<Int>>()
private var visited = booleanArrayOf()
private var result = 0

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (user, relationships) = readLine().split(" ").map { it.toInt() }
    graph = Array(user + 1) { mutableListOf() }
    visited = BooleanArray(user + 1)

    for (i in 0 until relationships) {
        val relationship = readLine().split(" ").map { it.toInt() }
        graph[relationship[0]].add(relationship[1])
        graph[relationship[1]].add(relationship[0])
    }

    var currentMin = Int.MAX_VALUE
    var answer = 0
    for (i in user downTo 1) {
        var totalRes = 0
        visited.fill(false)
        result = 0

        for (f in 1 .. user) {
            visited.fill(false)
            result = 0

            if (i == f) continue
            find(i, f)

            totalRes += result
        }

        val newMin = min(currentMin, totalRes)

        // 더 적은 케빈 베이컨 수를 구하기.
        if (newMin < currentMin) {
            currentMin = newMin
            answer = i
        }
        // 현재 i의 케빈 베이컨 수의 합과 현제 케빈 베이컨 수의 최솟갑과 같다면 i를 갱신해주기.
        else if (totalRes == currentMin) {
            answer = i
        }
    }

    println(answer)
}

private fun find(user: Int, toFind: Int) {
    val queue: Queue<List<Int>> = LinkedList()
    visited[user] = true

    for (u in graph[user]) {
        if (u == toFind) {
            result = 1
            return
        }
        queue.add(listOf(u, 1))
    }

    while (queue.isNotEmpty()) {
        val data = queue.poll()
        val checkUser = data[0]
        val level = data[1]

        for (g in graph[checkUser]) {
            if (!visited[g]) {
                if (g == toFind) {
                    result += level + 1
                    return
                }
                queue.add(listOf(g, level + 1))
                visited[g] = true
            }
        }
    }
}

 

문제 풀이

graph(2차원 List)에 입력값을 넣는다.

2차원 리스트의 첫 번째 index값은 user의 번호를 뜻하고, 첫 번째 index 안의 리스트는 user와 관계를 맺고 있는 다른 user들이다.

사진 1-2

graph의 구조는 사진 1-2와 같을 것이다.

visited는 1차원 리스트로 설정해 준다. 관계 그래프를 돌면서 몇 번째 user를 거쳤는지 확인해 주는 작업이기 때문에 2차원 리스트 타입으로 정의할 필요가 없다. 예를 들어 사진 1-2의 4번째 값은 1, 5, 3이 들어간 리스트인데, 여기에서 3이 이미 방문한 사용자라면 3을 제외한 1, 5만 보면 된다.

 

이제 2중 반복을 돌면서 bfs를 수행한다.

bfs에서는 현재 사용자(i)와 만나야 하는 사용자(f)가 주어진다.

처음에 queue에 graph의 i번째 index에 나오는 데이터를 target으로 반복문을 돌려서 queue에 넣어 준다. 만약 처음부터 찾아야 하는 값인 f가 있다면 결과를 1로 저장하고 꺼도 된다.

 

queue가 비어있지 않을 때까지 반복해 준다. 

비어 있지 않으면 개로 값을 넣어준다. 만약 처음부터 찾아야 하는 값인 onFind가 존재한다면 result를 1로 변경하고 함수를 종료한다.

아니면 queue가  비어있지 않을 때까지 반복한다.

bfs를 돌면서 사용자 번호를 통과했는지 아래의 조건으로 확인한다.

if (!visited[g])

이 조건이 만족하고 찾아야 하는 toFind와 같으면 result를 queue에서 뽑아온 데이터의 level의 + 1만큼 해준 값으로 설정한다.

마지막에 queue에 추가하고 방문 여부를 체크한다.

 

 

 

문제 해결 과정

그래프 구조를 짜서 bfs를 돌리는 문제이다.

사용자들 간의 관계를 그래프로 잘 표현해야 bfs를 쓸 때 편하다. 그것만 조금 생각하면 풀기 어렵지 않았다.