[백준] 24444 - 너비 우선 탐색 1

BFS 를 활용하는 문제.
무방향 그래프이기 때문에 visitedArr 을 추가하여 한 번 방문한 곳에는 다시 들리지 않도록 해야한다.

BFS, DFS 에 관한 내용은 이전 게시글 BFS, DFS 관련 게시글 를 참고하길 바란다.

풀이

/*
* 너비 우선 탐색이므로 반복문을 사용하기
* 무방향 그래프이므로 양방향이 가능하다. visited 사용하자
* 무방향 그래프이므로 Array<MutableList<*>> 사용하자
* 정점 n, 간선 M, 시작 정점 r
*
* 정점 번호는 1부터 N
* 인접 정점은 오름차순으로 방문
*
* */
fun `24444 - 너비 우선 탐색1`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val strBuilder = StringBuilder()
    val (n, m, r) = br.readLine().split(" ").map{ it.toInt() }
    val visitedArr = IntArray(n + 1)
    val undirectList = Array(n + 1){ mutableListOf<Int>() }
    val queue = ArrayDeque<Int>()
    var visitCount = 0

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

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

    undirectList.forEach { it.sort() }

    queue.add(r)
    visitedArr[r] = ++visitCount

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

        for(to in undirectList[from]){
            if(visitedArr[to] == 0){
                visitedArr[to] = ++visitCount
                queue.add(to)
            }
        }
    }

    for(i in 1 .. n){
        strBuilder.appendLine(visitedArr[i])
    }

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