[백준][KOTLIN][13023] ABCDE

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

13023번: ABCDE

문제 풀이

1. 주어진 친구 관계를 저장하는 인접 리스트 배열을 선언한다. (val friend = Array(N) { ArrayList<Int>() })

2. 친구의 수 0 부터 N-1 까지 반복하여 DFS 로 탐색한다. 이때 처음 시작되는 친구는 방문했으므로 visit[i] 를 true 로 설정하고 DFS 탐색한다.

3. depth 가 4 일 경우 주어진 조건과 같은 친구 관계가 되었으므로 결과를 1로 출력하고 그외에는 0으로 출력한다.

코드

import java.io.*

private var result = false

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    // N : 친구 수     (5<= N <= 2000)
    // M : 친구 관계 수 (1<= N <= 2000)
    val (N, M) = br.readLine().split(" ").map { it.toInt() }
    val friend = Array(N) {
        ArrayList<Int>()
    }

    repeat(M) {
        val (a, b) = br.readLine().split(" ").map { it.toInt() }
        // a - b 과 친구 관계이면 서로 친구사이이므로 양방향으로 값을 설정한다.
        friend[a].add(b)
        friend[b].add(a)
    }

    for (i in 0 until N) {
        val visit = BooleanArray(N) { false }
        visit[i] = true
        dfs(N, friend, visit, i, 0)

        if (result) {
            break
        }

        result = false
    }

    if (result) {
        println(1)
    } else {
        println(0)
    }
}

private fun dfs(N: Int, friend: Array<ArrayList<Int>>, visit: BooleanArray, start: Int, depth: Int) {
    if (depth == 4) {
        // 조건처럼 5명의 친구관계가 되면 조건을 만족한다.
        result = true
        return
    }

    //println("dfs $start, $depth")

    for (next in friend[start]) {
        if (!visit[next]) {
            visit[next] = true
            dfs(N, friend, visit, next, depth + 1)
            visit[next] = false
        }
    }
}