[백준 1260] DFS와 BFS

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

✍️ 첫번째 접근

Swift 언어에 익숙해지기 위하여, 현재까지 풀었던 문제 중 일부 + 새로운 문제를 풀어보아 알고리즘을 위한 Swift 문법과 아이디어를 공부할 예정이다. 이 문제는 이미 C++로 풀었던 경험이 있지만 Swift 문법을 익히고자 다시 풀게 되었다.
문제를 풀면서 주의할 점은 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 가장 작은 것을 먼저 방문해야 하는 조건을 염두해야 한다는 것이다.
알게된 사실

• readLine()은 한줄씩 입력받으므로 한줄에 공백 단위로 여러 값을 입력받을 경우 readLine()!.split(separator: " ").map { Int(String($0))! }를 사용한다.
• C++에서 자주 사용하던 Queue 자료구조가 존재하지 않는다. 그래서 직접 구현해야 하나..?라는 생각을 가졌지만 append(_:)와 removeFirst() 등 메서드가 존재하기 때문에 굳이 Queue를 구현할 필요없이 배열을 사용하여 해결했다.

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let N: Int = input[0]
let M: Int = input[1]
let V: Int = input[2]
var arr: [[Int]] = Array(repeating: [], count: 1005)
var visited: [Bool] = Array(repeating: false, count: 1005)
var ans: String = ""

for _ in 0..<M {
    let line = readLine()!.split(separator: " ").map { Int(String($0))! }
    arr[line[0]].append(line[1])
    arr[line[1]].append(line[0])
}
// 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 가장 작은 것을 먼저 방문해야 하므로 정렬
for i in 0..<arr.count {
    arr[i].sort()
}

func dfs(_ cur: Int) {
    visited[cur] = true
    ans += "\(cur) "
    for nxt in arr[cur] {
        if visited[nxt] {
            continue
        }
        dfs(nxt)
    }
}

func bfs(_ num: Int) {
    var Q: [Int] = [num]
    visited[num] = true
    while !Q.isEmpty {
        let cur = Q.removeFirst()
        ans += "\(cur) "
        for nxt in arr[cur] {
            if visited[nxt] {
                continue
            }
            Q.append(nxt)
            visited[nxt] = true
        }
    }
}

dfs(V)
print(ans)
visited = Array(repeating: false, count: N+1)
ans = ""
bfs(V)
print(ans)