[Algorithm] 백준 - 1260번 DFS와 BFS (Swift)

문제 소개

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

문제에서 아예 솔직하게 DFS, BFS로 탐색해봐라 라는 문제이다.
 

문제 풀이

BFS가 익숙하지 않아서 조금 어려움을 겪었다. 큐를 사용하여 BFS를 구현하였다.

import Foundation

let nmv = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n, m, v) = (nmv[0], nmv[1], nmv[2])

var graph = Array(repeating: Array(repeating: 0, count: n+1), count: n+1)

for _ in 0..<m {
    let ab = readLine()!.split(separator: " ").map { Int($0)! }
    let (a, b) = (ab[0], ab[1])
    
    graph[a][b] = 1
    graph[b][a] = 1
}

var visitForDFS = Array(repeating: false, count: n+1)
var visitForBFS = Array(repeating: false, count: n+1)

func dfs(_ v: Int) {
    visitForDFS[v] = true
    print(v, terminator: " ")
    for i in 1...n {
        if graph[v][i] == 1 && !visitForDFS[i] {
            dfs(i)
        }
    }
}

func bfs(_ v: Int) {
    var queue = [v]
    visitForBFS[v] = true
    while !queue.isEmpty {
        let poped = queue.removeFirst()
        print(poped, terminator: " ")
        for i in 1...n {
            if graph[poped][i] == 1 && !visitForBFS[i] {
                queue.append(i)
                visitForBFS[i] = true
            }
        }
    }
}

dfs(v)
print("")
bfs(v)