[백준] 1260번: DFS와 BFS - kotlin

문제

https://www.acmicpc.net/problem/1260

풀이

• DFS
  • 스택에 시작값을 넣는다.
  • 스택의 top 값을 빼내고 top 값과 연결되어 있고, 방문하지 않은 노드들을 push 한다.
  • 스택이 비어있을 때까지 반복한다.
• BFS
  • 큐에 시작값을 넣는다.
  • 큐의 dequeue 값을 빼내고 해당 값과 연결되어 있고, 방문하지 않은 노드들을 enqueue 한다.
  • 큐가 비어있을 때까지 반복한다.

import java.io.BufferedWriter

fun dfs(graph: Array<MutableList<Int>>, start: Int, bw: BufferedWriter, n: Int) {
    graph.forEach {
        it.sortDescending()
    }
    val visited = Array(n + 1) { false }
    val stack = mutableListOf<Int>()
    stack.add(start)
    bw.write("$start ")
    visited[start] = true
    while (stack.isNotEmpty()) {
        val top = stack.removeLast()
        if (!visited[top]) {
            bw.write("$top ")
            visited[top] = true
        }
        graph[top].forEach {
            if (!visited[it]) {
                stack.add(it)
            }
        }
    }
}

fun bfs(graph: Array<MutableList<Int>>, start: Int, bw: BufferedWriter, n: Int) {
    graph.forEach {
        it.sort()
    }
    val visited = Array(n + 1) { false }
    val queue = mutableListOf<Int>()
    queue.add(start)
    bw.write("$start ")
    visited[start] = true
    while (queue.isNotEmpty()) {
        val top = queue.removeFirst()
        graph[top].forEach {
            if (!visited[it]) {
                queue.add(it)
                bw.write("$it ")
                visited[it] = true
            }
        }
    }
}

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val (n, m, v) = br.readLine().toString().split(" ").map { it.toInt() }
    val graph = Array(n + 1) { mutableListOf<Int>() }
    repeat(m) {
        val (a, b) = br.readLine().toString().split(" ").map { it.toInt() }
        graph[a].add(b)
        graph[b].add(a)
    }
    dfs(graph, v, bw, n)
    bw.write("\n")
    bfs(graph, v, bw, n)
    br.close()
    bw.close()
}

더 좋은 풀이 방법 있으면 댓글 달아주세요!!!