[알고리즘] ABCDE (백준 13023번)

13023번: ABCDE

 문제 형태를 보면 알겠지만 DFS를 활용해서 depth를 파악해야하는 문제다. 처음엔 모든 노드들을 각각 시작점으로 하여서 한 번씩 DFS를 돌리려고 했는데 어째서인지 틀렸다고 나왔다.

 

Solution

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

import java.util.*
import kotlin.collections.ArrayList

var br = BufferedReader(InputStreamReader(System.`in`))
var bw = BufferedWriter(OutputStreamWriter(System.out))

var N = 0//정점 수
var M = 0//간선 수
var graph = ArrayList<ArrayList<Int>>()
lateinit var visited : BooleanArray
var result = 0

fun solution() {

    var strtok = StringTokenizer(br.readLine())
    N = strtok.nextToken().toInt()
    M = strtok.nextToken().toInt()


    visited = BooleanArray(N)

    for(i in 0 until N)
        graph.add(ArrayList())

    for(i in 0 until M)
    {
        strtok = StringTokenizer(br.readLine())
        var from = strtok.nextToken().toInt()
        var to = strtok.nextToken().toInt()

        graph.get(from).add(to)
        graph.get(to).add(from)
    }

    for(i in 0 until N)
    {
        if(!visited[i])
        {
            visited[i] = true
            dfs(i, 0, visited)
            visited[i] = false
        }
        if(result == 1)
            break
    }

    bw.write(result.toString())
}

fun dfs(now : Int, depth : Int, visited : BooleanArray)
{
    if(depth == 4)
    {
        result = 1
        return
    }

    for(i in 0 until graph[now].size)
    {
        var next = graph[now][i]

        if(!visited[next])
        {
            visited[next] = true
            dfs(next, depth + 1, visited)
            visited[next] = false 
        }
    }  
}

fun main() {
    solution()
    br.close()
    bw.close()
}

 아직까지도 완벽히 이해가 된 건 아닌데 depth가 더 깊어질 때마다 이미 방문했던 노드들도 다시 방문해서 depth를 맞춰야 되는 경우도 생길 수 있는 것이다.

 

만약 visited를 false 시켜주지 않았을 때 일어나는 예를 보자

 이 경우에 1 - 2 - 4 - 5 순서로 먼저 탐색을 했다고 치자. 그럼 2에서 3으로 다시 분기되서 탐색을 할 때 4는 이미 방문했기에 1 - 2 - 3 - 4 - 5로 조건이 성립됨에도 불구하고 4에서 탐색이 끝나버리는 것이다.