백준 14567번 선수과목 (Prerequisite) Kotlin

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

문제

---

생각하기

---

• 그래프 문제이다.
  • 위상 정렬 문제이다.

동작

    repeat(M) {
        st = StringTokenizer(br.readLine())
        val u = st.nextToken().toInt()
        val w = st.nextToken().toInt()

        adjList[u].add(w)
        inDegree[w]++ // 진입 차수
    }

inDegree[] 각 정점의 진입 차수 값을 저장한다.

    for (i in 1..N) {
        if (inDegree[i] == 0) { // 진입 차수가 0인 것 부터 시작
            que.addFirst(Edge(i, 1))
            ret[i] = 1
            isVisited[i] = true
        }
    }

    while (que.isNotEmpty()) {
        val cur = que.removeLast()

        for (next in adjList[cur.num]) {
            if (isVisited[next]) continue

            inDegree[next]--
            if (inDegree[next] == 0) { // 진입차수가 0이된 노드만 큐에 넣는다.
                ret[next] = cur.count + 1
                que.addFirst(Edge(next, cur.count + 1))
            }
        }
    }

진입 차수가 0이 된 노드만 큐에 넣고, 큐에서 꺼낸 노드는 다시 진입 차수가 0이 될 일이 없다.
ret[]에 각 노드별 차수를 저장해서 정답을 만든다.

결과

코드

---

import java.io.File
import java.util.StringTokenizer

// input
private var br = System.`in`.bufferedReader()

// variables
private var N = 0
private var M = 0
private lateinit var adjList: MutableList<MutableList<Int>>
private lateinit var inDegree: IntArray
private data class Edge(val num: Int, val count: Int)

fun main() {
    val bw = System.out.bufferedWriter()

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    val ret = BFS()
    for (i in 1..N) {
        sb.append(ret[i]).append(' ')
    }

    return sb.toString()
} // End of solve()

private fun BFS(): IntArray {
    val que = ArrayDeque<Edge>()
    val isVisited = BooleanArray(N + 1)
    val ret = IntArray(N + 1)

    for (i in 1..N) {
        if (inDegree[i] == 0) { // 진입 차수가 0인 것 부터 시작
            que.addFirst(Edge(i, 1))
            ret[i] = 1
            isVisited[i] = true
        }
    }

    while (que.isNotEmpty()) {
        val cur = que.removeLast()

        for (next in adjList[cur.num]) {
            if (isVisited[next]) continue

            inDegree[next]--
            if (inDegree[next] == 0) { // 진입차수가 0이된 노드만 큐에 넣는다.
                ret[next] = cur.count + 1
                que.addFirst(Edge(next, cur.count + 1))
            }
        }
    }

    return ret
} // End of BFS()

private fun input() {
    var st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt()
    M = st.nextToken().toInt()

    inDegree = IntArray(N + 1) // 차수
    adjList = mutableListOf()
    repeat(N + 1) {
        adjList.add(mutableListOf())
    }

    repeat(M) {
        st = StringTokenizer(br.readLine())
        val u = st.nextToken().toInt()
        val w = st.nextToken().toInt()

        adjList[u].add(w)
        inDegree[w]++ // 진입 차수
    }
} // End of input()