[swift] DFS

어제 백준 치킨거리 문제를 풀다가 아 이거 dfs 알고리즘을 쓰는거다!
했으나, swift 시작한지 거의 2일차...당장 2차원 배열도 공부 안했는데 ㅋㅋ dfs구현이요?!

그래도 당장 닥쳐왔을 때 공부하는게 기억에 남을 듯 하여 이번 기회에 DFS를 swift로 구현하는 방법을 알아보도록 하자.

let graph: [String: [String]] = [
	"A":["B", "C"],
    "B":["A", "D", "E"],
    "C":["A","F"],
    "D":["B"],
    "E":["B"],
    "F":["C"],
]

• 큐는 FIFO, 스택은 LIFO
  이렇게 인접 노드를 저장해둔 그래프가 있다.

1. 시작점인 A를 방문해야할 노드 스택에 넣는다.
2. 방문한 큐에 A가 존재하지 않으니, 방문해야할 노드 스택에서 pop
3. A를 방문한 큐에 추가하고, A와 인접한 노드들을 모두 방문해야할 노드에 추가한다.
4. 2,3 반복

DFS 알고리즘

1. 시작점을 스택에 푸시
2. 스택에서 노드를 pop
3. pop한 노드가 not visited -> 노드의 이웃노드 중 not visited를 스택에 푸시하고, pop한 노드를 방문 처리
4. 2,3에서 스택이 empty 될때까지 반복

코드출처

func DFS(graph: [String: [String]], start: String) -> [String] {
    var visitedQueue: [String] = []
    var needVisitStack: [String] = [start]
    
    while !needVisitStack.isEmpty {
        let node: String = needVisitStack.removeLast()
        if visitedQueue.contains(node) { continue }
        
        visitedQueue.append(node)
       needVisitStack += graph[node] ?? []
    }
    
    return visitedQueue
}