[백준] 24479 - 알고리즘 수업 - 깊이 우선 탐색 1

무방향 비가중치 그래프를 구현하고 DFS 를 활용하여 푸는 문제이다.
처음에는 지문에 대해 이해가 가지 않아, 해석을 보고 나서야 알았다.

풀이 1. (재귀 방식)

/*
* 무방향 비가중치 그래프
* u 와 v 의 값은 다르고, 모든 간선의 쌍 값도 다르다.
* 시작 정점은 1
* */

private lateinit var adjList: Array<MutableList<Int>>
private lateinit var visitedArr: IntArray
private var stringBuilder = StringBuilder()
private var visitCount = 0

fun `24479-알고리즘 수업 - 깊이 우선 탐색 1`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val graphToken = StringTokenizer(br.readLine())
    val n = graphToken.nextToken().toInt()
    val m = graphToken.nextToken().toInt()
    val r = graphToken.nextToken().toInt()

    /*
    * 인접 리스트 생성. 비가중치이므로 간선 가중치는 넣지 않음
    * 1-based Index 로 설정
    * */
    visitedArr = IntArray(n + 1){ visitCount }
    adjList = Array(n + 1){ mutableListOf() }

    repeat(m){
        val token = StringTokenizer(br.readLine())
        val u = token.nextToken().toInt()
        val v = token.nextToken().toInt()

        // 무방향이므로 양방향 추가
        adjList[u].add(v)
        adjList[v].add(u)
    }

    for(i in adjList.indices) adjList[i].sort()

    visit(r)

    for(i in 1 until visitedArr.size){
        stringBuilder.appendLine("${ visitedArr[i] }")
    }

    bw.write(stringBuilder.trim().toString())
    bw.flush()
    bw.close()
    br.close()
}

/*
* if(visitedArr[to] == 0) return 에서 for 문 내부에서 확인하는 거로 변경하였음.
* 함수 호출을 적게하여 시간을 더 빠르게 하기 위해 변경.
* */
private fun visit(from: Int){
    visitedArr[from] = ++visitCount
    for(to in adjList[from]){
        if(visitedArr[to] == 0) {
            visit(to)
        }
    }
}

풀이 2. (스택 방식)

private lateinit var adjList: Array<MutableList<Int>>
private lateinit var visitedArr: IntArray
private var stringBuilder = StringBuilder()
private var visitCount = 0

fun `24479-알고리즘 수업 - 깊이 우선 탐색 1`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val graphToken = StringTokenizer(br.readLine())
    val n = graphToken.nextToken().toInt()
    val m = graphToken.nextToken().toInt()
    val r = graphToken.nextToken().toInt()

    /*
    * 인접 리스트 생성. 비가중치이므로 간선 가중치는 넣지 않음
    * 1-based Index 로 설정
    * */
    visitedArr = IntArray(n + 1){ visitCount }
    adjList = Array(n + 1){ mutableListOf() }

    repeat(m){
        val token = StringTokenizer(br.readLine())
        val u = token.nextToken().toInt()
        val v = token.nextToken().toInt()

        // 무방향이므로 양방향 추가
        adjList[u].add(v)
        adjList[v].add(u)
    }

    for(i in adjList.indices) adjList[i].sort()

    visitIterative(r)

    for(i in 1 until visitedArr.size){
        stringBuilder.appendLine("${ visitedArr[i] }")
    }

    bw.write(stringBuilder.trim().toString())
    bw.flush()
    bw.close()
    br.close()
}

private fun visitIterative(startNode: Int) {
    val stack = ArrayDeque<Int>()
    stack.addLast(startNode)

    while (stack.isNotEmpty()) {
        val from = stack.removeLast()

        if (visitedArr[from] != 0) {
            continue
        }

        visitedArr[from] = ++visitCount

        // ★★★ 핵심: 역순으로 스택에 넣어야 오름차순으로 방문 가능 ★★★
        for (i in adjList[from].indices.reversed()) {
            val to = adjList[from][i]
            if (visitedArr[to] == 0) {
                stack.addLast(to)
            }
        }
    }
}

후기

처음에는 재귀적으로 푸는 방식으로 문제를 해결하였으나, 더 효율적인 해결 방식이 없을까 싶어 AI 에게 물어 본 결과 N 이 10만이나 되므로 StackOverFlow 에 빠질 수 있어 풀이 2번째 방식인 Stack 방식을 추천하였다.

왜 StackOverFlow 에 대해서 생각하지 못했을까.
코딩 테스트를 보는 경우 위험한 상황이 나올 수 있으니 Stack 을 이용하여 푸는 방식을 활용해봐야겠다.