문제 링크 (opens new window)

풀이

import Foundation

struct Queue<T> {
    var array: [T?] = []
    var head = 0

    var isEmpty: Bool {
        return count == 0
    }

    var count: Int {
        return array.count - head
    }

    mutating func enqueue(_ element: T) {
        array.append(element)
    }

    mutating func dequeue() -> T? {
        guard head < array.count,
              let element = array[head] else { return nil }
        array[head] = nil
        head += 1

        let percentage = Double(head) / Double(array.count)
        if array.count > 50 && percentage > 0.25 {
            array.removeFirst(head)
            head = 0
        }

        return element
    }

    var front: T? {
        if isEmpty {
            return nil
        } else {
            return array[head]
        }
    }
}

var visited: [Bool] = .init(repeating: false, count: 1050)
var graph: [[Int]] = .init(repeating: [], count: 1050)

let input = readLine()!.split(separator: " ").map { Int($0)! }
let N = input[0]; let M = input[1]; let V = input[2]

func dfs(_ here: Int) {
    print(here, terminator: " ")
    visited[here] = true

    for there in graph[here] {
        if visited[there] { continue }

        dfs(there)
    }
}

func bfs(_ start: Int) {
    var q = Queue<Int>()
    q.enqueue(start)
    visited[start] = true

    while !q.isEmpty {
        guard let here = q.dequeue() else { return }

        print(here, terminator: " ")

        for there in graph[here] {
            if visited[there] { continue }
            q.enqueue(there)
            visited[there] = true
        }
    }
}

for _ in 0..<M {
    let edge = readLine()!.split(separator: " ").map { Int($0)! }
    graph[edge[0]].append(edge[1])
    graph[edge[1]].append(edge[0])
}

for (index, _) in graph.enumerated() {
    graph[index].sort()
}

dfs(V)
visited = .init(repeating: false, count: 1050)
print()
bfs(V)