백준 13023번
https://www.acmicpc.net/problem/13023
백트래킹 DFS문제이다.
노드간에 다리를 하나씩 건너서 서로 모두 연결되어 이동할 수 있는가에 대한 문제인줄 알았더니, 그냥 연속으로 5개가되는 노드가 있는지를 묻는 문제였다.
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