[백준] 1260 - DFS와 BFS

지금까지 배운 DFS, BFS 를 종합하여 출력하는 문제이다.
시간을 짧게 사용하기 위해 공용으로 사용할 변수를 1개 선언하여 사용하였다.

풀이

/*
* 정점 번호가 작은 것부터 방문이므로 오름차순
* 양방향 그래프.
* 정점 번호는 1 ~ N
*
* 첫째줄 DFS, 둘째줄 BFS.
* 정점 N, 간선 M, 시작점 V
*
* 방문하는 정점을 순서대로 출력해야한다.
* */

private lateinit var adjacencyList: Array<MutableList<Int>>
private lateinit var visitedArr: BooleanArray
private var stringBuilder = StringBuilder()
private val dequeue = ArrayDeque<Int>()

fun `1260-DFS와 BFS`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val (n, m, v) = br.readLine().split(" ").map { it.toInt() }

    adjacencyList = Array(n + 1){ mutableListOf()}
    visitedArr = BooleanArray(n + 1)

    repeat(m){
        val token = java.util.StringTokenizer(br.readLine())
        val from = token.nextToken().toInt()
        val to = token.nextToken().toInt()

        adjacencyList[from].add(to)
        adjacencyList[to].add(from)
    }

    // 인접리스트 오름차순 정렬 후 dfs 진행
    adjacencyList.forEach { it.sort() }

    dfs(v)

    // 초기화 및 줄넘김 처리
    dequeue.fill(0)
    visitedArr.fill(false)
    stringBuilder.append("\n")

    bfs(v)

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

private fun dfs(from: Int){
    dequeue.addLast(from)

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

        if(visitedArr[from]) continue

        visitedArr[from] = true

        if(stringBuilder.isNotEmpty()){
            stringBuilder.append(" ")
        }
        stringBuilder.append("${from}")

        for(to in adjacencyList[from].asReversed()){
            if(!visitedArr[to]){
                dequeue.addLast(to)
            }
        }
    }
}

private fun bfs(from: Int){
    dequeue.addFirst(from)
    visitedArr[from] = true
    stringBuilder.append("${from}")

    while (dequeue.isNotEmpty()){
        val from = dequeue.removeFirst()

        for(to in adjacencyList[from]){
            if(!visitedArr[to]){
                visitedArr[to] = true
                stringBuilder.append(" ${to}")
                dequeue.addLast(to)
            }
        }
    }
}

후기

DFS, BFS 두 개를 구현하여 풀이하고, 반복문으로 풀이하다보니 add 및 remove 를 언제해야할지 헷갈려 몇 번 틀렸다.
문제의 지문도 잘못읽어 방문 정점을 출력하는 것이 아닌, 순서로 출력하여 틀리기도 하였고 dfs 에서 visited 처리의 위치도 잘못 놓아 틀리기도 하였다.

문제의 지문을 잘 읽고, 자체적으로 테스트 케이스를 주어 풀이하는 습관을 더 들여야 할 것 같다.