백준 24479번
https://www.acmicpc.net/problem/24479

문제

---

생각하기

---

• DFS 기초 문제이다.
  • 그래프 정렬이 포함되어 있음

동작

코드

---

Kotlin

import java.io.*
import java.util.*

// input
private lateinit var br: BufferedReader
private lateinit var sb: StringBuilder

// variables
private var N = 0 // 정점의 수
private var M = 0 // 간선의 수
private var R = 0 // 시작 정점

// 방문 여부 체크
private lateinit var isVisited: IntArray
private var visitCount = 1

// adjList
private lateinit var adjList: MutableList<ArrayList<Int>>

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))
    sb = StringBuilder()

    // input
    input()

    DFS(R)
    for (i in 1..N) {
        sb.append(isVisited[i]).append('\n')
    }

    bw.write(sb.toString())
    bw.close()
} // End of main

private fun DFS(index: Int) {
    isVisited[index] = visitCount++// 방문 여부

    val size = adjList[index].size
    for (i in 0 until size) {
        if (isVisited[adjList[index][i]] == 0) {
            DFS(adjList[index][i])
        }
    }
} // End of DfS

private fun input() {
    var st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt() // 정점의 수
    M = st.nextToken().toInt() // 간선의 수
    R = st.nextToken().toInt() // 시작 정점

    isVisited = IntArray(N + 1) // 0 ~ M

    adjList = ArrayList()
    for (i in 0..N) {
        adjList.add(ArrayList())
    }

    for (i in 0 until M) {
        st = StringTokenizer(br.readLine())
        val u = st.nextToken().toInt() // 정점
        val v = st.nextToken().toInt() // 정점

        adjList[u].add(v)
        adjList[v].add(u)
    }

    for (i in 1..N) {
        adjList[i].sort()
    }
} // End of input