[백준] 13023번: ABCDE - Kotlin[코틀린]

문제

 

13023번: ABCDE

 

---

풀이

 

 이 문제는 5명의 친구관계가 연결되어 있는 것을 찾는 문제로, DFS와 백트래킹을 이용하여 depth가 5인 관계를 찾으면 된다.

 

 먼저, 친구관계를 입력받아 양방향으로 연결된 그래프를 생성한다. 그리고 모든 노드에 대한 DFS 탐색을 수행한다. DFS 탐색은 백트래킹을 이용하여 방문했던 노드에서 연결된 노드가 있을 경우 방문 체크를 해준 뒤 DFS를 수행한다. DFS 수행 이후 방문한 노드의 상태를 방문하지 않은 것으로 다시 바꿔준다. 탐색 중 DFS의 depth가 5가 되는 경우, 5명의 친구가 연결되었다고 판단하고 check 변수를 true로 만들어 준다. check 변수에 따라 1 또는 0을 출력해준다.

 

---

코드

 

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val st = StringTokenizer(br.readLine())
    val num = st.nextToken().toInt()
    val case = st.nextToken().toInt()

    val graph = List(num) { mutableListOf<Int>() }

    repeat(case) {
        with(StringTokenizer(br.readLine())) {
            val start = nextToken().toInt()
            val end = nextToken().toInt()
            graph[start].add(end)
            graph[end].add(start)
        }
    }

    lateinit var visited : BooleanArray
    var check = false

    fun dfs(depth: Int, idx: Int) {
        if(depth == 5 || check) { // 5명의 친구 연결
            check = true
            return
        }

        graph[idx].forEach {
            if(!visited[it]) { // 백트래킹
                visited[it] = true
                dfs(depth + 1, it)
                visited[it] = false
            }
        }
    }

    for(i in 0 until num) { // 모든 노드에 대해 DFS 수행
        visited = BooleanArray(num)
        visited[i] = true
        dfs(1, i)
    }

    bw.write(if(check) "1" else "0")
    bw.flush()
    bw.close()
    br.close()
}