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

문제

---

생각하기

---

• 오일러 경로 문제이다.

  • degree배열에 각 노드 오차를 계산하는데, 홀수 오차가 2개나 0개면 가능하고 그렇지 않으면 불가능 한 것으로 판단한다.

• 인접리스트로 구현했다

• DFS를 통해서 한번에 모든 노드를 방문할 수 있는지 체크한다.

  • count가 1이 아니면 한번에 돌지 못한 것이므로 "NO"를 출력하면 된다.

동작

코드

---

Kotlin

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


// input
private lateinit var br: BufferedReader
private lateinit var bw: BufferedWriter

// variables
private var V = 0
private var E = 0

private lateinit var adjacencyList: MutableList<MutableList<Int>>
private lateinit var isVisited: BooleanArray

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    bw = BufferedWriter(OutputStreamWriter(System.out))
    val sb = StringBuilder()
    
    if (input() == "NO") {
        bw.write("NO")
        bw.close()
        return
    }

    var count = 0
    for (i in 1..V) {
        if (isVisited[i]) continue
        DFS(i)
        count++
        if (count > 1) break
    }

    if (count != 1) sb.append("NO")
    else sb.append("YES")

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

private fun DFS(node: Int) {
    if (isVisited[node]) return
    isVisited[node] = true

    adjacencyList[node].forEach {
        DFS(it)
    }
} // End of DFS

private fun check(degree: IntArray): String {
    var odd = 0
    for (i in 1..V) {
        if (degree[i] % 2 != 0) {
            odd++
        }
    }

    if (odd == 0 || odd == 2) {
        return "YES"
    } else {
        return "NO"
    }
} // End of check

private fun input(): String {
    var st = StringTokenizer(br.readLine())
    V = st.nextToken().toInt() // 지점의 개수
    E = st.nextToken().toInt() // 연결 구간의 개수

    isVisited = BooleanArray(V + 1)
    val degree = IntArray(V + 1)

    // 단방향 그래프
    adjacencyList = ArrayList()
    repeat(V + 1) {
        adjacencyList.add(ArrayList())
    }

    repeat(E) {
        st = StringTokenizer(br.readLine())
        val u = st.nextToken().toInt()
        val v = st.nextToken().toInt()
        adjacencyList[u].add(v)
        adjacencyList[v].add(u)
        degree[u]++
        degree[v]++
    }

    return check(degree)
} // End of input