[백준/BOJ] 2644번: 촌수계산

문제

https://www.acmicpc.net/problem/2644

2644번: 촌수계산

해설

부모자식 관계가 성립하는지를 저장하기 위해 ArrayList<ArrayList<Int>>라는 자료형을 가진 graph를 선언하였다.

부모자식을 양방향으로 모두 저장하였다면 dfs를 통해 찾고자 하는 두 사람의 관계가 나올 때까지 dfs 알고리즘을 수행하면 된다.

코드

private lateinit var visited: BooleanArray
private val graph = ArrayList<ArrayList<Int>>()
private var ans = -1

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    visited = BooleanArray(n + 1)
    repeat(n + 1) {
        graph.add(ArrayList())
    }

    val (p1, p2) = readLine().split(" ").map { it.toInt() }
    val pairCnt = readLine().toInt()

    repeat(pairCnt) {
        val (a, b) = readLine().split(" ").map { it.toInt() }
        graph[a].add(b)
        graph[b].add(a)
    }

    dfs(p1, p2, 0)

    println(ans)
}

private fun dfs(start: Int, end: Int, cnt: Int) {
    if(start == end) {
        ans = cnt
        return
    }

    visited[start] = true
    for(next in graph[start]) {
        if(!visited[next]) {
            visited[next] = true
            dfs(next, end, cnt + 1)
        }
    }
}