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

문제

---

생각하기

---

• 오일러 경로 문제이다.

• 인접리스트로 구현했다

  • 인접행렬 구현시 cnt를 빼가면서, 0 이상일 때 조건만 넣어주면 되지만, 메모리 낭비와 탐색시간이 늘어나서 인접리스트를 통해서 구현했다.
  • 인접리스트는 cnt가 0이 될 때 removeAt()을 통해서 리스트 데이터를 지워가면서 경로를 찾아간다.

동작

코드

---

Kotlin

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


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

// variables
private var N = 0
private lateinit var adjList: MutableList<MutableList<Node>>

private data class Node(var num: Int, var cnt: Int)

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

    if (!input()) {
        sb.append(-1)
        bw.write(sb.toString())
        bw.close()
        return
    }

    euler(1)

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

private fun euler(node: Int) {
    var idx = 0
    while (adjList[node].isNotEmpty()) {
        val nextNode = adjList[node][idx].num

        var idx2 = 0
        while (adjList[nextNode].isNotEmpty()) {
            if (adjList[nextNode][idx2].num == node) {
                adjList[nextNode][idx2].cnt--
                if (adjList[nextNode][idx2].cnt == 0) {
                    adjList[nextNode].removeAt(idx2)
                }
                break
            }
            idx2++
        }

        adjList[node][idx].cnt--
        if (adjList[node][idx].cnt == 0) {
            adjList[node].removeAt(idx--)
        }

        euler(nextNode)
        idx++
    }

    sb.append(node).append(' ')
} // End of DFS

private fun input(): Boolean {
    N = br.readLine().toInt()

    adjList = ArrayList()
    repeat(N + 1) {
        adjList.add(ArrayList())
    }

    for (i in 1..N) {
        val st = StringTokenizer(br.readLine())
        var sum = 0
        for (j in 1..N) {
            val temp = st.nextToken().toInt()

            if (i < j && temp > 0) {
                adjList[i].add(Node(j, temp))
                adjList[j].add(Node(i, temp))
            }
            sum += temp
        }

        // 그래프의 한 노드에서 차수가 하나라도 홀수 일 경우 오일러회로가 불가능하다.
        // 모든 정점의 차수가 짝수가 되어야 함 하나라도 짝수가 되지 않으면 오일러 회로가 불가능하다.
        // 두개 이상의 컴포넌트로 분리가 되면 안된다.
        if (sum % 2 != 0) {
            return false
        }
    }

    return true
} // End of input