Swift를 통한 DFS, BFS의 구현

DFS의 재귀, 비재귀적 구현
BFS의 구현
WFS(DFS와 BFS의 통합)의 구현을 해보았다.
DispatchQueue를 오랜만에 다시 써보기도 했고 serialQueue와 concurrentQueue의 동작방식, 초기화 방법 등에 대해서도 다시 공부해보았다.
/*
 DFS, BFS의 기본 원리,
 DispatchQueue와 Generic등을 복습하면서 작성해보았다.
 DFS와 BFS를 WFS로 통합하여 작성해보기도 했다.
 백준 1260 DFS와 BFS 문제의 출력과 동일하게 맞춰주려면
 다음에 탐색할 Node를 선정할때 후보가 여러개라면
 가장 낮은 숫자의 Node를 선정하는 방식의 로직을 추가해주면 된다.
 */

import Dispatch

let nmv = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = nmv[0]
let m = nmv[1]
let v = nmv[2]
var graph = Array.init(repeating: Array.init(repeating: 0, count: 0), count: n)
var visitedForDFS = Array.init(repeating: false, count: n)
var visitedForBFS = Array.init(repeating: false, count: n)
var visitedForWFS = Array.init(repeating: false, count: n)

var wfsAnswer = [Int]()

for _ in 0..<m {
    let temp = readLine()!.split(separator: " ").map { Int(String($0))! }
    graph[temp[0]-1].append(temp[1]-1)
    graph[temp[1]-1].append(temp[0]-1)
}

var dfsAnswer = [Int]()
var queue = [Int]()
var bfsAnswer = [Int]()

protocol Bag {
    func isEmpty() -> Bool // 빈 bag 체크는 사용자가
    func push(x: Int)
    func pop() -> Int
    func top() -> Int
}

class Stack: Bag {
    private var stack = [Int]()

    func isEmpty() -> Bool {
        return stack.isEmpty
    }

    func push(x: Int) {
        stack.append(x)
    }

    func pop() -> Int {
        return stack.removeLast()
    }

    func top() -> Int {
        return stack.last!
    }
}

class Queue: Bag {
    private var queue = [Int]()

    func isEmpty() -> Bool {
        return queue.isEmpty
    }

    func push(x: Int) {
        queue.append(x)
    }

    func pop() -> Int {
        return queue.removeFirst()
    }

    func top() -> Int {
        return queue.first!
    }
}

// DFS의 재귀를 통한 구현
func DFSWithBag(x: Int){
    visitedForDFS[x] = true
    dfsAnswer.append(x)

    graph[x].forEach {
        if visitedForDFS[$0] == false {
            DFSWithBag(x: $0)
        }
    }
}

// BFS의 재귀 X 구현
func BFSWithBag(x: Int) {
    let queue = Queue()
    queue.push(x: x)
    visitedForBFS[x] = true
    bfsAnswer.append(x)

    while !queue.isEmpty() {
        let nextNode = queue.pop()

        if visitedForBFS[nextNode] == false {
            visitedForBFS[nextNode] = true
            bfsAnswer.append(nextNode)
        }

        graph[nextNode].forEach {
            if visitedForBFS[$0] == false {
                queue.push(x: $0)
            }
        }
    }
}

// WhateverFirstSearch
// bag에 queue를 넣어주면 BFS, stack을 넣어주면 DFS로 작동
// 재귀 X 방식으로 구현
func WFS(x: Int, bag: Bag) {
    bag.push(x: x)
    visitedForWFS[x] = true
    wfsAnswer.append(x)

    while !bag.isEmpty() {
        let nextNode = bag.pop()

        if visitedForWFS[nextNode] == false {
            visitedForWFS[nextNode] = true
            wfsAnswer.append(nextNode)
        }

        graph[nextNode].forEach {
            if visitedForWFS[$0] == false {
                bag.push(x: $0)
            }
        }
    }
}


// attributes 프로퍼티를 default 값인 []로 두면 serialQueue가 만들어진다.
let serialQueue = DispatchQueue(label: "serialQueue")

// DFS, BFS는 순서에 상관없이 동시에 수행되어도 괜찮다.
serialQueue.async {
    DFSWithBag(x: v-1)
    BFSWithBag(x: v-1)
}

/*
 DFS와 BFS가 실행된 이후에 (serialQueue에 넣어준 이후)
 print문이 순서에 맞게 실행되어야 하므로 (sync의 이유)
 Q. 그럼 그냥 serialQueue에 안넣어주면 안되나요?
 A. 그러면 print문들이 DFS BFS가 완료되기 전에 호출되므로 안돼요
 */

serialQueue.sync {
    print(dfsAnswer.map { String($0+1) }.joined(separator: " "))
    print(bfsAnswer.map { String($0+1) }.joined(separator: " "))
}
Swift를 통한 DFS, BFS의 구현

CATALOG

FEATURED TAGS
