[Swift] BOJ 2252 줄 세우기

BOJ 2252 줄 세우기

 

✅ 위상 정렬 문제이다.

아래에 있을수록 먼저 제출

 

진짜 많이도 틀렸다.

1. 2개의 틀렸습니다. 알고리즘 후에 마지막으로 출력할 때 1 2 3으로 해야하는걸 [1,2,3]으로 반환했기에 이를 수정해주었다.

2. 시간초과 3개는 동일 알고리즘에서 시간 초과가 나서 readLine 부분을 수정하였다.

처음에 readLine 부분을 개선하니 11%에서 시간초과 나던게 15%에서 시간초과가 나니 약간의 개선 효과는 있었던 듯 싶다.

// 시간초과 11%
readLine()!.split(separator: " ").map { Int($0)! }
// 시간초과 15% (개선코드)
readLine()!.split(separator: " ").map { Int(String($0))! }

 

3. 맞았습니다. 문제는 input시에 딕셔너리에 입력하는 부분이었다.

// 시간초과가 나는 코드
            if graph[info[0]] == nil {
                graph[info[0]] = [info[1]]
            } else {
                var temp = graph[info[0]]!
                temp.append(info[1])
                graph[info[0]]!.append(temp)
                
            }

// 개선한 코드 (맞았습니다.)
            if graph[info[0]] == nil {
                graph[info[0]] = [info[1]]
            } else {
                graph[info[0]]!.append(info[1])
            }

 

 

✅ 통과 ㅎㅎ..ㅎㅎ

import Foundation
// 0: 학생수 1: 주어지는 정보 반복 수
        let input = readLine()!.split(separator: " ").map { Int($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($0)! }

            if graph[info[0]] == nil {
                graph[info[0]] = [info[1]]
            } else {
                var temp = graph[info[0]]!
                temp.append(info[1])
                graph[info[0]] = temp
            }

            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.count > index {
            let now = queue[index]
            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())

 

 

 

다른 사람의 코드도 있는데, 이분의 스타일도 알아두면 좋겠다.

 

(참고)

https://woongsios.tistory.com/218

백준 2252 줄 세우기