[Swift] BOJ 1766 문제집

BOJ 1766 문제집

 

✅ 이것도 위상정렬 문제입니다. 위상정렬 알고리즘은 쉬운데 어느때에 사용해야할 지 판단하는게 중요하다.

 

물론 위상정렬 알고리즘 포스팅에도 적어 두었지만, 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것'이다. 

쉽게 말해서 선수과목 같은 조건이 있는 경우에 사용한다.

 

 

✅ 코드

알고리즘은 줄 세우기 알고리즘과 같다.

다만, queue를 sort해야하는 부분만 조금 다르며, queue의 경우에는 줄 세우기는 데이터가 커서 index로 접근하지만 이 문제에서는 removeFirst로 처리한다. 

2022.05.24 - [코딩테스트] - [Swift] BOJ 2252 줄 세우기

//https://www.acmicpc.net/problem/1766
import Foundation

struct b1766 {
    static func run() {
        // 0: 학생수 1: 주어지는 정보 반복 수
        let input = readLine()!.split(separator: " ").map { Int(String($0))! }
        
        var graph = [Int: [Int]]() // 비교하는 학생에 대한 정보
        
        var indegree = [Int](repeating: 0, count: input[0]+1) // 진입차수 정보
        indegree[0] = -1 // index를 학생번호로 쓰기 위함.
        
        for _ in 0..<input[1] {
            let info = readLine()!.split(separator: " ").map { Int(String($0))! }
            
            if graph[info[0]] == nil {
                graph[info[0]] = [info[1]]
            } else {
                graph[info[0]]!.append(info[1])
            }
            
            indegree[info[1]] += 1
        }
        
//        print(graph)
//        print(indegree)
        
        var queue = [Int]()
        indegree.enumerated().forEach {
            if $0.element == 0 {
                queue.append($0.offset)
            }
        }
//        print(queue)
        
        
        var result = [Int]()
        // 큐가 빌때까지
        
//        var index = 0
        while !queue.isEmpty {
//            let now = queue[index]
            queue.sort(by: <)
            let now = queue.removeFirst()
//            index += 1
            result.append(now)
            
            // 해당원소와 연결된 노드들의 진입차수에서 -1
            if let sequence = graph[now] {
                for i in sequence{
                    indegree[i] -= 1
                    
                    if indegree[i] == 0 {
                        queue.append(i)
                    }
                }
            }
            
        }
        
        //        print(result)
        print(result.reduce(into: "", { $0 += "\($1) "}).dropLast())
    }
}