[백준 1260] DFS와 BFS (Kotlin)

문제

https://www.acmicpc.net/submit/1260/48093515

코드

import java.lang.Math.*
import java.util.*
import kotlin.collections.ArrayList
import kotlin.collections.HashMap

private val br = System.`in`.bufferedReader()

fun bfs(start: Int){
  var q = ArrayDeque<Int>()
  q.add(start)
  visit[start] = true
  print("$start ")

  while(!q.isEmpty()){
    val curr = q.poll()
    graph[curr].forEach{ nextNode ->
         if (!visit[nextNode]){
           visit[nextNode] = true
           q.add(nextNode)
           print("$nextNode ")
         }
    }
  }
}

fun dfs(curr: Int){
  visit[curr] = true
  print("$curr ")

  graph[curr].forEach{ nextNode ->
    if(!visit[nextNode]){
      visit[nextNode] = true
      dfs(nextNode)
    }
  }
}

var graph = mutableListOf<MutableList<Int>>()
var visit = booleanArrayOf()

fun main() {
  val (n, m, v) = br.readLine().split(' ').map { it.toInt() }
  graph = MutableList(n+1) { mutableListOf<Int>() }
  visit = BooleanArray(n+1)

  repeat(m){
    val (y,x) = br.readLine().split(' ').map{it.toInt()}
    graph[y].add(x)
    graph[x].add(y)
  }

  for(i in 1 until n+1){
    graph[i].sort()
  }
  dfs(v)
  println()
  visit.fill(false)
  bfs(v)
}

• 그래프는 인접 리스트를 이용해 구현했다. 리스트 안에 리스트를 넣어주면 됨.
• dfs는 재귀, bfs는 deque를 이용해 구현했다.
• 코틀린으로 그래프 문제를 풀 때 참고하려고 풀은 문제. 이 코드를 베이스로 나머지 그래프 문제도 풀을 예정이다.