[Swift] 백준 1260 DFS와 BFS (Graph Traversal)

 

📌 풀이

💬 Code

import Foundation

struct Queue<T> {
    fileprivate var array = [T]()

    public var isEmpty: Bool {
        return array.isEmpty
    }

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

    public mutating func dequeue() -> T? {
        if isEmpty {
            return nil
        } else {
            return array.removeFirst()
        }
    }
}

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

var graph = Array<[Int]>(repeating: [], count: n+1)
var visited = Array<Bool>(repeating: false, count: n+1)
var queue = Queue<Int>()

// 그래프 초기화
for _ in 0..<m {
    let line = readLine()!.split(separator: " ").map { Int(String($0))! }
    let v1 = line[0]
    let v2 = line[1]
    graph[v1].append(v2)
    graph[v2].append(v1)
    graph[v1].sort()
    graph[v2].sort()
}

dfs(start: v)

visited = Array<Bool>(repeating: false, count: n+1)
print("")

bfs(start: v)

// DFS
func dfs(start: Int) {
    visited[start] = true
    print(start, terminator: " ")
    for i in graph[start] {
        if !visited[i] {
            dfs(start: i)
        }
    }
}

// BFS
func bfs(start: Int) {
    queue.enqueue(start)
    visited[start] = true

    while !queue.isEmpty {
        guard let v = queue.dequeue() else { return }
        print(v, terminator: " ")
        for i in graph[v] {
            if !visited[i] {
                queue.enqueue(i)
                visited[i] = true
            }
        }
    }
}

 

 

1260번: DFS와 BFS