BOJ-1260 DFS와 BFS Swift

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

내가 푼 풀이

- DFS 와 BFS 알고리즘으로 푼다.

- 정점이 여러개면, 접점 번호가 작은 것부터 먼저 방문한다

- DFS는 Dictionary에서 마지막원소를 빼므로 내림차순, BFS는 첫 번째 원소를 빼므로 오름차순으로 정렬한다.

 

import Foundation

let inputs = readLine()!.split(separator: " ").map{ Int($0)! }
var dict = [Int: [Int]]()

// 그래프 입력
for i in 0..<inputs[1] {
    let input = readLine()!.split(separator: " ").map{ Int($0)! }
    if dict[input[0]] == nil {
        dict[input[0]] = [input[1]]
    } else if !dict[input[0]]!.contains(input[1]) {
        dict[input[0]]!.append(input[1])
    }
    if dict[input[1]] == nil {
        dict[input[1]] = [input[0]]
    } else if !dict[input[1]]!.contains(input[0]) {
        dict[input[1]]!.append(input[0])
    }
}

var visitedQueue = [Int]()
var visitedQueue2 = [Int]()
var needVisitStack = [inputs[2]]

// DFS
// 인접한 접점번호가 작은순이므로, 접점번호가 저장된배열을 내림차순으로 정렬한다.
while !needVisitStack.isEmpty {
    let node = needVisitStack.removeLast()
    if visitedQueue.contains(node) { continue }
    
    visitedQueue.append(node)
    needVisitStack += dict[node]?.sorted{ $0 > $1 } ?? []
}

// BFS
// 인접한 접점번호가 작은순이므로, 접점번호가 저장된배열을 오름차순으로 정렬한다.
needVisitStack = [inputs[2]]
while !needVisitStack.isEmpty {
    let node = needVisitStack.removeFirst()
    if visitedQueue2.contains(node) { continue }
    
    visitedQueue2.append(node)
    needVisitStack += dict[node]?.sorted{ $0 < $1 } ?? []
}

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