[백준 2252] 줄 세우기 (Swift)

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

 

위상정렬

우선! 키 순서대로 줄을 세우는 아주 불쾌한 문제입니다!

하지만 덕분에 위상정렬을 배우게 되었어요. 그나마 제 몫을 하는 문제였습니다 후

키 순서대로 줄을 세우지만, 키는 알려주지 않고 두명의 학생을 비교해서 둘의 순서 만 알려주네요 그것도 몇명만

어쨌든 알려진 키 순서를 어기지만 않게 1번부터 N번까지의 학생들을 차례로 나타내면 되는 문제입니다.

 

접근방법

위상정렬을 사용해서 풀이하는 문제인데요.

위상정렬은, 원소들을 정렬하는 데 순서가 있고, 이를 지켜서 정렬할 수 있도록 만들어진 알고리즘인 것 같습니다.

이 문제에서 순서는 내가 줄 서기 위해서 내 앞에 먼저 서야하는 학생들이 더는 없는지. 를 확인하는 것이라고 생각하면 될 것 같습니다.

무슨 소리냐면, 1 < 3, 2 < 3 이라는 키 순서가 주어졌을 때 (N = 3), 1과 2는 줄을 서기 전에 나보다 앞에 서야하는 친구가 정해져 있지 않습니다. 따라서 바로 정렬시킬 수 있습니다. 그치만 3은 내가 줄 서기 전에 줄을 서야하는 친구가 2명이 있는 것임 = 2명이 줄을 서줘야 (빠져줘야) 내가 줄을 설 수 있음

 

1. 그래서 내가 줄 서기 전에 먼저 줄세워야 하는 친구의 수를 degrees 배열에 하나씩 저장해줍니다.

(ex. 1 : 0, 2 : 0, 3 : 2) 이런식이 됨.

2. degree가 0인 학생부터 줄을 세우는 데, 그럼 줄을 선 학생은 이제 반대로 내가 줄서야만 줄을 설 수 있었던 친구 (나보다 큰애)를 줄 설 수 있게 해줘야겠죠 -> 줄을 섰으면, 나보다 큰 친구의 degree를 하나씩 빼줍니다. (나 줄 섰으니까 이제 너 줄 서도 돼 약간 이런ㅇㅇ)

(근데 이제 위의 예시의 3처럼 1이 줄 서고 3한테 너 줄서도 돼 라고 했는데, 3: 아냐 나 아직 한명 더 남았어;, 라고 할 수도 있습니다 쨌든)

3. 그럼 한차례 degree가 0인 친구들이 줄을 서면 또 degree가 0인 친구들이 생길거에요. 그럼 이 친구들도 줄을 세워주면 됩니다.

queue에 담고 큐에서 빼면서 줄세우고 나보다 큰 애 degree 빼주고 한다는 측면에서 bfs 같은 문제라고 할 수 있겠어요

4. 큐가 비면 모두 줄을 섰을 겁니다.

 

오답노트

백준은 출력 형식이 1 2 3 이런식으로 출력해야해서 swift에서 배열을 바로 출력해버리면 틀리더라고요 (한 2%에서 틀림 앞부분은 무슨 테스트였을까)

그래서 이번에는 고차함수를 사용해서 map과 string을 " "공백으로 joined하는 걸로 출력했습니다.

 

소스코드

import Foundation

func solution() -> [Int] {
    let input = readLine()!.split(separator:" ").map{Int($0)!}
    let N:Int = input[0]
    let M:Int = input[1]
    var degrees:[Int] = Array<Int>(repeating: 0, count: N+1)

    var adj:[[Int]] = Array<Array<Int>>(repeating: [], count:N+1)

    for _ in 0..<M {
        let line = readLine()!.split(separator:" ").map{Int($0)}
        let A = line[0]!
        let B = line[1]!
        degrees[B] += 1
        adj[A].append(B)
    }
    
    var q:[Int] = []
    for i in 1...N {
        if degrees[i] == 0 {
            q.append(i)
        }
    }
    
    var result:[Int] = []
    while(!q.isEmpty) {
        let now = q[0]
        q.removeFirst()
        result.append(now)
        
        for next in adj[now] {
            degrees[next] -= 1
            if degrees[next] == 0 {
                q.append(next)
            }
        }
    }
    
    return result
}


print(solution().map {String($0)}.joined(separator: " "))