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

24479 - 깊이 우선 탐색에서 정렬 순서만 변경된 문제이다.
Array.sort() 를 Array.sortByDescending { it } 으로 변경해주자.

풀이 1 - 재귀 방식

import java.lang.StringBuilder
import java.util.StringTokenizer

private lateinit var graph: Array<MutableList<Int>>
private lateinit var visitVertexArr: IntArray
private var strBuilder = StringBuilder()
private var visitCount = 0

fun `24480-알고리즘 수업-깊이 우선 탐색2`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val (n, m, r) = br.readLine().split(" ").map { it.toInt() }
    graph = Array(n + 1){ mutableListOf() }
    visitVertexArr = IntArray(n + 1)

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

        graph[u].add(v)
        graph[v].add(u)
    }

    for(i in 1 until graph.size) graph[i].sortByDescending { it }

    recursionDfs(r)

    for(i in 1 until visitVertexArr.size) strBuilder.appendLine(visitVertexArr[i])

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

// 재귀 방식
private fun recursionDfs(from: Int){
    visitVertexArr[from] = ++visitCount
    for(to in graph[from]){
        if(visitVertexArr[to] == 0) {
            recursionDfs(to)
        }
    }
}

풀이 2 - 스택 방식

import java.lang.StringBuilder
import java.util.StringTokenizer

private lateinit var graph: Array<MutableList<Int>>
private lateinit var visitVertexArr: IntArray
private var strBuilder = StringBuilder()
private var visitCount = 0

fun `24480-알고리즘 수업-깊이 우선 탐색2`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val (n, m, r) = br.readLine().split(" ").map { it.toInt() }
    graph = Array(n + 1){ mutableListOf() }
    visitVertexArr = IntArray(n + 1)

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

        graph[u].add(v)
        graph[v].add(u)
    }

    for(i in 1 until graph.size) graph[i].sortByDescending { it }

    stackDfs(r)

    for(i in 1 until visitVertexArr.size) strBuilder.appendLine(visitVertexArr[i])

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

// 스택 방식
private fun stackDfs(start: Int){
    val stack = ArrayDeque<Int>()
    stack.addLast(start)

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

        if(visitVertexArr[from] != 0) continue

        visitVertexArr[from] = ++visitCount

        /*
        * DFS 방식으로 처리하기 위해 (깊이로 들어가기 위해) asReversed() 처리.
        * */
        for(to in graph[from].asReversed()){
            if(visitVertexArr[to] == 0) stack.addLast(to)
        }
    }
}