Graph 탐색, Depth First Search

Graph 깊이 우선 탐색(Depth First Search, DFS)을 stack을 이용하여 풀 수 있다.

가장 중요한 부분은 노드 방문 여부(marked)를 확인하는 부분이다.

위와 같은 그래프가 있을 때, 탐색 순서는 다음과 같다.

• 노드 0을 방문, 노드 0의 이웃인 1,2,3을 스택에 푸시함
• 스택에 가장 위에 있는 노드 3을 방문함
• 그 다음 스택에 가장 위에 있는 노드인 2를 방문함, 노드 2의 이웃인 5,4를 푸시함
• 노드 4를 방문함
• 노드 5를 방문함, 노드 5의 이웃인 1을 방문함
• 스택에는 1이 남아 있지만, 이미 방문하였으므로 방문하지 않음

Swift 풀이

// MARK: - Graph Definition
class Node {
    var val: Int
    var marked: Bool = false
    var adjacent: [Node]?
    init(_ val: Int) { self.val = val }
    init(_ val: Int, _ adjacent: [Node]) { self.val = val; self.adjacent = adjacent }
}

// MARK: - DFS using Stack
func dfs_stack(_ root: Node) {
    var stack = [Node]()
    stack.append(root)

    while !stack.isEmpty {
        let node = stack.removeFirst()
        if node.marked == false {
            node.marked = true
            visit(node)
        }

        guard let adjcent = node.adjacent else { continue }
        for adj in adjcent {
            if adj.marked == false {
                stack.insert(adj, at: 0)
            }
        }
    }
}


let node3_0 = Node(0)
let node3_1 = Node(1)
let node3_2 = Node(2)
let node3_3 = Node(3)
let node3_4 = Node(4)
let node3_5 = Node(5)

node3_0.adjacent = [node3_1, node3_2, node3_3]
node3_2.adjacent = [node3_4, node3_5]
node3_5.adjacent = [node3_1]
// 0,3,2,5,1,4
dfs_stack(node3_0)