백준 - DFS와 BFS(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/1260

 

[문제 설명]

단순하게 bfs와 dfs로 그래프를 탐색하면 된다.

단!! 자식들부터 작은 수부터 탐색한다.

 

[접근 방법]

이 문제를 풀었는데 생각보다 진~짜 시간이 오래 걸렸다.  이유는 우선순위큐를 착각했기 때문.

우선순위큐의 경우(최소힙일 때) 루트가 최솟값인 것은 맞다.

그러나, 이들이 정렬되어 저장되어 있지는 않다. 

3,4,2,5,9,1과 같은 원소들을 저장하면 최상단 부모에는 1이 있는 건 확실하지만 1,2,3,4,5,9처럼 정렬 되어 저장되지는 않는다는 것이다.

따라서 최솟값을 계속 조회하려면 poll과 remove 과정에서 트리를 정렬하는 작업이 필요하다.

 

나는 이걸 모르고, Priority Queue에 무작정 값을 넣고, 인덱스로 접근하는 실수를 저질렀다.

예제에는 데이터가 몇개 되지 않아서, 우연히 데이터가 모두 정렬된것처럼 들어갔지만, 제출하니 작동이 되지 않았다.

차라리 TreeSet을 쓰거나, 그래프를 정렬한 후 작업하는 게 맞았을 것 같다.

그래서 정렬하고 푸니까 작동됐다.

 

[수정한 Kotlin 코드]

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (cntOfNode, cntOfDegree, positionOfStartNode) = readLine().split(" ").map { it -> it.toInt() }
    val graph = Array<LinkedList<Int>>(cntOfNode) {LinkedList()}

    for (noOfDegree in 0 until cntOfDegree) {
        val (startNode, endNode) = readLine().split(" ").map { it.toInt()-1 }
        graph[startNode].add(endNode)
        graph[endNode].add(startNode)
    }

    graph.map { it.sort() }
    var isVisited = BooleanArray(cntOfNode)
    println(dfs(StringBuilder(), positionOfStartNode-1, graph, isVisited))
    isVisited = BooleanArray(cntOfNode)
    println(bfs(positionOfStartNode-1, graph, isVisited))
}

fun dfs(
    answer: StringBuilder,
    positionOfStartNode: Int,
    graph: Array<LinkedList<Int>>,
    visited: BooleanArray
): StringBuilder {
    if (visited[positionOfStartNode]) {
        return answer
    }

    visited[positionOfStartNode] = true
    answer.append(positionOfStartNode+1).append(" ")
    graph[positionOfStartNode].forEach { nextPosition ->
        answer.append(dfs(StringBuilder(), nextPosition, graph, visited))
    }

    return answer
}

fun bfs(
    positionOfStartNode: Int,
    graph: Array<LinkedList<Int>>,
    visited: BooleanArray
): StringBuilder {
    val sb = StringBuilder()
    val queue = LinkedList<Int>()
    sb.append(positionOfStartNode+1).append(" ")
    visited[positionOfStartNode] = true

    queue.offer(positionOfStartNode)
    while (!queue.isEmpty()) {
        val currentNode = queue.poll()

        graph[currentNode].forEach { nextNode ->
            if (!visited[nextNode]) {
                queue.offer(nextNode)
                sb.append(nextNode+1).append(" ")
                visited[nextNode] = true
            }
        }
    }

    return sb
}

 

코틀린을 쓰면서 느끼는 거지만, 진짜 좋은 언어 같다.

자바와 호환도 되고, Null처리부터 코드의 간결함까지 아주 좋다.