[백준][Kotlin]1260번 DFS와 BFS

해당 문제는 DFS와 BFS 둘 다 구현을 할 줄 안다면 간단하게 작성 할 수 있는 문제였습니다.

사람에 따라 문제 내 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고 해당 조건을

sort 혹은 해당 인덱스에 별도의 값을 저장하여 작성하는 차이등이 있을거라 예상이 되며, 저는 sort기능을 사용하여

코드를 작성하였습니다. 제한 조건이 빡빡하였을 경우는 저도 인덱스에 별도의 값을 저장하여 작성하였었겠지만, 시간제한이 2초 인것을 확인하고 sort를 사용하였습니다.

 

하기는 제가 작성한 코드와 제출 결과 입니다.

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

lateinit var visit : BooleanArray
lateinit var node : Array<ArrayList<Int>>
var bw = BufferedWriter(OutputStreamWriter(System.out))

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    var st = StringTokenizer(br.readLine())
    val N = st.nextToken().toInt()
    val M = st.nextToken().toInt()
    val start = st.nextToken().toInt()

    node = Array(N+1,{ArrayList<Int>()})

    repeat(M){
        st = StringTokenizer(br.readLine())
        val one = st.nextToken().toInt()
        val two = st.nextToken().toInt()
        node[one].add(two)
        node[two].add(one)
    }

    for(arr in node){
        arr.sort()
    }

    visit = BooleanArray(N+1){true}
    dfs(start)
    bw.appendLine()

    visit = BooleanArray(N+1){true}
    var dq = ArrayDeque<Int>()
    dq.add(start)
    visit[start] = false
    while(!dq.isEmpty()){
        val now = dq.pollFirst()
        bw.append("$now ")
        for(i in 0 .. node[now].size-1){
            if(visit[node[now][i]]){
                dq.addLast(node[now][i])
                visit[node[now][i]] = false
            }
        }
    }
    
    bw.flush()
    bw.close()
}

fun dfs(now: Int){
    visit[now] = false
    bw.append("$now ")
    for(i in 0 .. node[now].size-1){
        if(visit[node[now][i]]){
            dfs(node[now][i])
        }
    }
}