백준 13023번
https://www.acmicpc.net/problem/13023

문제

---

생각하기

---

• 백트래킹 DFS문제이다.

• 노드간에 다리를 하나씩 건너서 서로 모두 연결되어 이동할 수 있는가에 대한 문제인줄 알았더니, 그냥 연속으로 5개가되는 노드가 있는지를 묻는 문제였다.
  

동작

코드

---

Kotlin

import java.io.*
import java.util.*

// input
private lateinit var br: BufferedReader
private lateinit var sb: StringBuilder

// variables
private var N = 0
private var M = 0

private lateinit var isVisited: BooleanArray
private lateinit var adjList: MutableList<MutableList<Int>>

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))
    sb = StringBuilder()

    input()

    solve()

    bw.write(sb.toString())
    bw.close()
} // End of main

private fun solve() {
    for (i in 0 until N) {
        if (DFS(i, 0)) {
            sb.append(1)
            return
        }
    }

    sb.append(0)
} // End of sovle

private fun DFS(cur: Int, depth: Int): Boolean {
    if (depth == 4) return true
    isVisited[cur] = true
    var ret = false

    for (nextCur in adjList[cur]) {
        if (isVisited[nextCur]) continue
        if (DFS(nextCur, depth + 1)) {
            ret = true
            break
        }
    }

    isVisited[cur] = false
    return ret
} // End of DFS

private fun input() {
    var st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt()
    M = st.nextToken().toInt()
    isVisited = BooleanArray(N)

    adjList = ArrayList()
    for (i in 0 until N) {
        adjList.add(ArrayList())
    }

    for (i in 0 until M) {
        st = StringTokenizer(br.readLine())
        val a = st.nextToken().toInt()
        val b = st.nextToken().toInt()

        adjList[a].add(b)
        adjList[b].add(a)
    }
} // End of input