백준 14567 - 선수 과목 (Kotlin)

백준 14567 - 선수 과목 (코틀린)

 

문제

올해 Z대학 컴퓨터공학부에 새로 입학한 민욱이는 학부에 개설된 모든 전공과목을 듣고 졸업하려는 원대한 목표를 세웠다.

어떤 과목들은 선수과목이 있어 해당되는 모든 과목을 먼저 이수해야만 해당 과목을 이수할 수 있게 되어 있다.

공학인증을 포기할 수 없는 불쌍한 민욱이는 선수과목 조건을 반드시 지켜야만 한다.

민욱이는 선수과목 조건을 지킬 경우 각각의 전공과목을 언제 이수할 수 있는지 궁금해졌다.

계산을 편리하게 하기 위해 아래와 같이 조건을 간소화하여 계산하기로 하였다.

1. 한 학기에 들을 수 있는 과목 수에는 제한이 없다.
2. 모든 과목은 매 학기 항상 개설된다.

모든 과목에 대해 각 과목을 이수하려면 최소 몇 학기가 걸리는지 계산하는 프로그램을 작성하여라.

 

---

입력

첫 번째 줄에 과목의 수 N(1 ≤ N ≤ 1000)과 선수 조건의 수 M(0 ≤ M ≤ 500000)이 주어진다.

선수과목 조건은 M개의 줄에 걸쳐 한 줄에 정수 A B 형태로 주어진다.

A번 과목이 B번 과목의 선수과목이다. A < B인 입력만 주어진다. (1 ≤ A < B ≤ N)

 

---

출력

1번 과목부터 N번 과목까지 차례대로 최소 몇 학기에 이수할 수 있는지를 한 줄에 공백으로 구분하여 출력한다.

 

---

알고리즘 분류

• 다이나믹 프로그래밍
• 위상 정렬
• 그래프 이론
• 방향 비순환 그래프

---

해설

이번 문제는 다이나믹 프로그래밍(DP)를 이용하여 해결하였다.

 

이번 문제를 해결하기 위하여 subjects 라는 2차원 배열을 만들어 주었다.

subjects[x][y] 에서 subjects[x] 에는 x 과목의 선행과목이 저장되어 있다.

 

예를 들어 x 과목의 선행 과목이 a, b 라면 subjects[x] = [a, b] 가 된다.

만약 선행 과목이 없다면 subjects[x] = [] 로 비어있게 될 것이다.

 

이것을 이용하여 해결하였다.

1..N 까지 탐색한다.

• 만약 subjects[i] 가 비어있다면 선행과목이 없으므로 dp[i] = 1 이 된다.
• 만약 비어있지 않다면 해당 과목의 선행 과목들의 최소 이수 학기 중 가장 큰 값을 구해야 한다.
  예를 들어 subjects[4] = [2, 3] 라면 dp[2] = 1, dp[3] = 2 중 최대값인 dp[3] + 1 해주고 dp[4] 에 넣어준다. dp[4] = dp[3] + 1

---

전체 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (N, M) = br.readLine().split(" ").map { it.toInt() }
    var dp = Array(N + 1) { 0 }
    val subjects = Array<MutableList<Int>>(N + 1) { mutableListOf() }

    repeat(M) {
        val (start, end) = br.readLine().split(" ").map { it.toInt() }
        subjects[end].add(start)
    }

    for(i in 1..N){
        if(subjects[i].isEmpty()) {
            dp[i] = 1
        } else{
            var max = 0

            for(j in subjects[i].indices){
                max = maxOf(max, dp[subjects[i][j]])
            }

            dp[i] = max + 1
        }
    }

    for(i in 1..N){
        print("${dp[i]} ")
    }
}

 

---

정답

 

이번 문제를 보고 그냥 생각나는데로 대충 코드로 만들어 봤는데 바로 정답처리되서 당황했다....

다른 사람 풀이를 보니 위상정렬을 많이 사용했다.

나도 위상 정렬을 공부하고 후에 다시 풀어봐야겠다.