14567번: 선수과목

 

선수과목 (Prerequisite) 

 

문제

올해 Z대학 컴퓨터공학부에 새로 입학한 민욱이는 학부에 개설된 모든 전공과목을 듣고 졸업하려는 원대한 목표를 세웠다. 어떤 과목들은 선수과목이 있어 해당되는 모든 과목을 먼저 이수해야만 해당 과목을 이수할 수 있게 되어 있다. 공학인증을 포기할 수 없는 불쌍한 민욱이는 선수과목 조건을 반드시 지켜야만 한다. 민욱이는 선수과목 조건을 지킬 경우 각각의 전공과목을 언제 이수할 수 있는지 궁금해졌다. 계산을 편리하게 하기 위해 아래와 같이 조건을 간소화하여 계산하기로 하였다.

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

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

입력

첫 번째 줄에 과목의 수 N(1 ≤ N ≤ 1000)과 선수 조건의 수 M(0 ≤ M ≤ 500000)이 주어진다. 선수과목 조건은 M개의 줄에 걸쳐 한 줄에 정수 A B 형태로 주어진다. A번 과목이 B번 과목의 선수과목이다. A < B인 입력만 주어진다. (1 ≤ A < B ≤ N)

출력

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

예제 입력 1 

3 2
2 3
1 2

예제 출력 1 

1 2 3

예제 입력 2 

6 4
1 2
1 3
2 5
4 5

예제 출력 2 

1 2 2 1 3 1

 

---

풀이

 

먼저 문제를 이해해 보자.

 

• 한 학기에 들을 수 있는 과목 제한이 없다.
• 모든 과목은 매 학기 개설된다.
• 선수과목 조건이 있는 과목이 있다.
• 모든 과목을 이수하는 데 걸리는 최소학기를 구해라.

 

문제에서 중요한 것은 선수과목이다. 

 

처음 생각

 

 

일단 처음에 생각한 것은 "그냥 무작정 탐색을 해보자"였다. 시간제한이 5초여서 무작정 탐색을 해도 가능하다고 생각했다.

 

예제 2를 살펴보면 선수과목 조건을 다음과 같이 정리할 수 있다.

 

 

 

arr배열에 선수과목을 연결해 주었다. 

 

 

계속 arr를 탐색을 하면서 빈값을 가졌다면 store [] 배열에 넣고 store[] 배열의 값을 선수과목으로 가지는 과목을 삭제한다.

 

예를 들어, 처음에 1,4,6의 값이 빈값이니 1을 store[]배열에 넣고 1을 선수과목으로 가지는 arr [] 배열의 값을 삭제한다.

그러면 arr[2]와 arr[3]은 빈값이 되니, 2와 3을 다시 store에 넣고 탐색하는 것이다.

 

 

작성한 코드는 다음과 같다. 

let input = readLine()!.split(separator: " ").map{Int($0)!}

let (N,M) = (input[0],input[1])

var arr = [[Int]](repeating: [Int](repeating: 0, count: 0), count: N+1)
var result = [Int](repeating: 1, count: N+1)
var store: [Int] = []

var semester = 2

for _ in 0..<M{
    let subjectArr = readLine()!.split(separator: " ").map { Int($0)!}
    let (a,b) = (subjectArr[0],subjectArr[1])
    arr[b].append(a)
}

while arr.contains(where: { !$0.isEmpty }){
    store.removeAll()
    for i in 1..<N+1{
        if arr[i].isEmpty{
            store.append(i)
        }else{

        }
    }
    find()
    semester+=1
    
}

func find(){
    for i in 1..<N+1{
        for num in arr[i]{
            if store.contains(num){
                result[i] = semester
                arr[i].remove(at: arr[i].firstIndex(of: num)!)
               
            }
        }
    }
}
for i in 1..<N+1{
    print(result[i], terminator: " ")
}

 

딱 봐도 시간복잡도가 아주 난리가 날 것 같아서 확인해 봤다.

 

• for _ in 0..<M 의 readLine()에서 입력처리에 대한 복잡도 O(N+M)
• while arr.contains()에서 모든 배열 확인 O(N)
• find() 함수 O(N)

 

전체 시간복잡도는 대략 O((N+M) * N^2)이다.

최악의 시간복잡도는 O(501000 + 250000000000)정도로 엄청나게 큰 시간을 잡아먹고 있다는 걸 알 수 있다.

 

너무 코드를 막 작성한 탓이다,,,

---

설계

 

블로그를 찾아보면서 이 문제가 위상정렬 알고리즘을 사용한다는 것을 알게 되었다.

 

예제 1을 다음과 같이 설명할 수 있다.

 

 

내가 설계한 것에서 arr[]에 저장하는 선수과목의 위치를 바꿔서 저장해 보자.

선수과목을 1로 가지는 2,3과목을 arr[1]배열에 연결해 주는 것이다.

 

 

 

그다음 해당 과목이 선수과목을 몇 개 가지는 지 배열에 저장해 주자.

 

• inDegree[] : 선수과목이 몇 개인지 저장

 

 

 

 

---

구현

 

위의 설계를 바탕으로 queue를 사용하여 구현하였다.

 

1️⃣ 초기 설정

 

• arr[] 배열에 해당 index를 선수과목으로 가지는 값 연결
• inDegree[] 배열에 선수과목을 가지는 과목의 개수 증가

 

 

 

2️⃣ 초기 선수과목이 없는 과목 체크

 

• 선수과목이 없는 과목은 queue에 추가

 

 

 

3️⃣ 학기 판단

 

 

• 저장된 queue의 값을 선수과목으로 가지는 next 값을 판단하고 inDegree에 -1해준다.

 

 

 

다음과 같이 동작하게 된다.

 

 

---

전체코드

 

let input = readLine()!.split(separator: " ").map { Int($0)! }

let (N, M) = (input[0], input[1])

var arr = [[Int]](repeating: [Int](), count: N + 1)
var result = [Int](repeating: 0, count: N + 1)
var inDegree = [Int](repeating: 0, count: N + 1)
var queue: [Int] = []

for _ in 0..<M {
    let subjectArr = readLine()!.split(separator: " ").map { Int($0)! }
    let (a, b) = (subjectArr[0], subjectArr[1])
    arr[a].append(b)
    inDegree[b] += 1
}

for i in 1...N {
    if inDegree[i] == 0 {
        queue.append(i)
        result[i] = 1
    }
}

while !queue.isEmpty {
    let node = queue.removeFirst()
    for next in arr[node] {
        inDegree[next] -= 1
        if inDegree[next] == 0 {
            queue.append(next)
            result[next] = result[node] + 1
        }
    }
}

for i in 1...N {
    print(result[i], terminator: " ")
}