[백준] 촌수계산 (2644)(kotlin)

문제 설명

백준 2644번 문제 링크

입력 및 출력

» 입력

• 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다. 각 사람의 부모는 최대 한 명만 주어진다.

» 출력

입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다.

예제 입출력(테스트케이스)

입력	출력
9 7 3 7 1 2 1 3 2 7 2 8 2 9 4 5 4 6	3
9 8 6 7 1 2 1 3 2 7 2 8 2 9 4 5 4 6	-1

문제 풀이1

var n = 0
var inputs = 0
var p1 = 0
var p2 = 0
var map = arrayOf<BooleanArray>()
var check = arrayOf<BooleanArray>()
val list = mutableListOf<Int>()

fun main() = with(System.`in`.bufferedReader()) {
    n = readLine().toInt()
    readLine().split(" ").also {
            p1 = it[0].toInt()
            p2 = it[1].toInt()
        }

    inputs = readLine().toInt()
    map = Array(n + 1) { BooleanArray(n + 1) }
    check = Array(n + 1) { BooleanArray(n + 1) }

    repeat(inputs) {
        val (i1, i2) = readLine().split(" ").map { it.toInt() }
        map[i1][i2] = true
        map[i2][i1] = true
    }

    for (i in 1..n) {
        if (map[p1][i]) {
            check[p1][i] = true
            check[i][p1] = true
            dfs(i, 1)
            check[p1][i] = false
            check[i][p1] = false
        }
    }

    println(
        if (list.isNotEmpty()) list.minOf { it }
        else -1
    )
}

fun dfs(p1: Int, chon: Int) {
    if (p1 == p2) {
        list.add(chon)
    } else {
        for (i in 1..n) {
            if (map[p1][i] && !check[p1][i]) {
                check[p1][i] = true
                check[i][p1] = true
                dfs(i, chon + 1)
                check[p1][i] = false
                check[i][p1] = false
            }
        }
    }
}