[Swift] 백준 - DFS와 BFS

백준 링크 : https://www.acmicpc.net/problem/1260

 

참고 : 이것이 코딩테스트다 with 파이썬

import Foundation

let array = readLine()!.split(separator: " ").map { Int($0)! }
let nodesCount = array[0] // N
let edgesCount = array[1] // M
let start = array[2] // V

// 1. 그래프 세팅
var graph: [[Int]] = Array(repeating: [Int](), count: nodesCount + 1) // [] [1, 2] ...

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

for (i, g) in graph.enumerated() { // 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문
    graph[i] = g.sorted()
}


//2. dfs
var dfsVisited: [Bool] = Array(repeating: false, count: nodesCount + 1)

func dfs(_ node: Int) {
    dfsVisited[node] = true
    print(node, terminator: " ")
    
    for i in graph[node] {
        if dfsVisited[i] == false {
            dfs(i)
        }
    }
}

dfs(start)
print()

//3. bfs
var bfsQueue = [Int]()
var bfsVisited: [Bool] = Array(repeating: false, count: nodesCount + 1)

func bfs(_ node: Int) {
    bfsQueue.append(node)
    bfsVisited[node] = true
    
    while !bfsQueue.isEmpty {
        let node = bfsQueue.removeFirst()
        print(node, terminator: " ")
        
        for i in graph[node] {
            if bfsVisited[i] == false {
                bfsQueue.append(i)
                bfsVisited[i] = true
            }
        }
    }
}

bfs(start)