DFS와 BFS

Swift

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

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

 출력
 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
 
 예제 입력 1
 4 5 1
 1 2
 1 3
 1 4
 2 4
 3 4
 예제 출력 1
 1 2 4 3
 1 2 3 4
 예제 입력 2
 5 5 3
 5 4
 5 2
 1 2
 3 4
 3 1
 예제 출력 2
 3 1 2 5 4
 3 1 4 2 5
 예제 입력 3
 1000 1 1000
 999 1000
 예제 출력 3
 1000 999
 1000 999
 */
import Foundation

func dfs(n: Int, graph: [Int: [Int]], beginnigNode: Int, visit: (_ node: Int) -> Void) {
    var visited = [Bool](repeating: false, count: n)
    func dfsInternal(visitingNode: Int, visit: (_ node: Int) -> Void) {
        visited[visitingNode - 1] = true
        visit(visitingNode)
        graph[visitingNode]?.sorted().forEach { adjacentNode in
            if !visited[adjacentNode - 1] {
                dfsInternal(visitingNode: adjacentNode, visit: visit)
            }
        }
    }
    dfsInternal(visitingNode: beginnigNode, visit: visit)
}

func bfs(n: Int, graph: [Int: [Int]], beginnigNode: Int, visit: (_ node: Int) -> Void) {
    var queue = [Int]()
    var visited = [Bool](repeating: false, count: n)
    queue.append(beginnigNode)
    visited[beginnigNode - 1] = true
    
    while !queue.isEmpty {
        let (visitingNode) = queue.removeFirst()
        visit(visitingNode)
        
        graph[visitingNode]?.sorted().forEach { adjacentNode in
            guard !visited[adjacentNode - 1] else { return }
            queue.append(adjacentNode)
            visited[adjacentNode - 1] = true
        }
    }
}

func solution(n: Int, v: Int, edges: [[Int]]) {
    var graph = [Int: [Int]]()
    edges.forEach { edge in
        if graph[edge[0]] == nil {
            graph[edge[0]] = []
        }
        graph[edge[0]]?.append(edge[1])
        if graph[edge[1]] == nil {
            graph[edge[1]] = []
        }
        graph[edge[1]]?.append(edge[0])
    }
    var dfsResult = [Int]()
    dfs(n: n, graph: graph, beginnigNode: v) { node in
        dfsResult.append(node)
    }
    var bfsResult = [Int]()
    bfs(n: n, graph: graph, beginnigNode: v) { node in
        bfsResult.append(node)
    }
    print(dfsResult.map { "\($0)" }.joined(separator: " "))
    print(bfsResult.map { "\($0)" }.joined(separator: " "))
}

#if RANDOM
let n = Int.random(in: 1...5)
let m = Int.random(in: 1...10)
let v = Int.random(in: 1...n)
var edgeset: Set<[Int]> = []
for _ in 0..<m {
    var a = 0
    var b = 0
    while edgeset.contains([a, b]) || a == b {
        a = Int.random(in: 1...n)
        b = Int.random(in: 1...n)
    }
    edgeset.insert([a, b])
}
let edges = edgeset.map { $0 }
print("\(n) \(m) \(v)")
edges.forEach { print("\($0[0]) \($0[1])") }
#elseif FILEINPUT
final class FileIO {
    private let buffer:[UInt8]
    private var index: Int = 0

    init(fileHandle: FileHandle = FileHandle.standardInput) {
        
        buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
    }

    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }

        return buffer[index]
    }

    @inline(__always) func readInt() -> Int {
        var sum = 0
        var now = read()
        var isPositive = true

        while now == 10
                || now == 32 { now = read() } // 공백과 줄바꿈 무시
        if now == 45 { isPositive.toggle(); now = read() } // 음수 처리
        while now >= 48, now <= 57 {
            sum = sum * 10 + Int(now-48)
            now = read()
        }

        return sum * (isPositive ? 1:-1)
    }

    @inline(__always) func readString() -> String {
        var now = read()

        while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
        let beginIndex = index-1

        while now != 10,
              now != 32,
              now != 0 { now = read() }

        return String(bytes: Array(buffer[beginIndex..<(index-1)]), encoding: .ascii)!
    }

    @inline(__always) func readByteSequenceWithoutSpaceAndLineFeed() -> [UInt8] {
        var now = read()

        while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
        let beginIndex = index-1

        while now != 10,
              now != 32,
              now != 0 { now = read() }

        return Array(buffer[beginIndex..<(index-1)])
    }
}
let io = FileIO()
let n = io.readInt()
let m = io.readInt()
let v = io.readInt()
var edges: [[Int]] = []
for _ in 0..<m {
    edges.append([io.readInt(), io.readInt()])
}
#else
let input1 = readLine()?.split(separator: " ").map { Int($0) ?? 0 } ?? []
let n = input1[0]
let m = input1[1]
let v = input1[2]
var edges: [[Int]] = []
for _ in 0..<m {
    edges.append(readLine()?.split(separator: " ").map { Int($0) ?? 0 } ?? [])
}
#endif
solution(n: n, v: v, edges: edges)