[이것이 코딩 테스트다] chapter 5. DFS/BFS

chapter 5. DFS/BFS

 

✅ DFS/BFS에 대해서 알아보자!

 

DFS/BFS는 인공지능 수업시간에 공부했어서 그 개념은 알고 있었지만, 코드로 작성해 본 경험은 예전에 급하게 문제를 풀 때를 제외하곤 없었다.

알고리즘을 풀면서 DFS/BFS는 음.. 뭐랄까,  재귀나 완전탐색 등 다른 방법으로도 풀리는 문제들도 있었는데 가끔은 DFS/BFS가 아니면 풀 수 없겠는 문제(아니면 매우 복잡한)가 많더라.

그래서 공부해봄

 

 

✅ DFS

DFS는 깊이 우선 탐색 알고리즘이다. 이 알고리즘은 특정한 경로로 탐색하다가 특정 상황에서는 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가서 다른 경로로 탐색하는 경로로 탐색하는 알고리즘이다.

 

import Foundation

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

struct DFS_Module {
    static let graph: [String: [String]] = [
        "A" : ["B", "C"],
        "B" : ["A", "D", "E"],
        "C" : ["A", "F"],
        "D" : ["B"],
        "E" : ["B"],
        "F" : ["C"],
    ]
    
    static func run() {
        print(DFS(graph: graph, start: "A")) // ["A", "C", "F", "B", "E", "D"]
    }
}

 

 

✅ BFS

BFS는 너비 우선 탐색 알고리즘이다. 큐의 자료구조를 이용하여 선입선출 방식으로 구한다. 실제 수행 시간은 DFS보다 좋은편이다.

 

* 왜 DFS보다 BFS에서 더 좋은가?

-> 재귀로 DFS를 구현한다면 컴퓨터 시스템의 동작 특성상 실제 프로그램의 수행 시간은 느려질 수 있다. 따라서 스택 라이브러리를 이용해 시간 복잡도를 완화하는 테크닉이 필요할 때도 있다. 

 

import Foundation

public func BFS<T> (graph: [T: [T]], start: T) -> [T] {
    var visitedQueue: [T] = []
    var needVisitQueue: [T] = [start]
    
    while !needVisitQueue.isEmpty {
        let node: T = needVisitQueue.removeFirst()
        if visitedQueue.contains(node) { continue }
        
        visitedQueue.append(node)
        needVisitQueue += graph[node] ?? []
    }
    
    return visitedQueue
}

struct BFS_Module {
    static let graph: [String: [String]] = [
        "A" : ["B", "C"],
        "B" : ["A", "D", "E"],
        "C" : ["A", "F"],
        "D" : ["B"],
        "E" : ["B"],
        "F" : ["C"],
    ]
    
    static func run() {
        print(BFS(graph: graph, start: "A")) // ["A", "B", "C", "D", "E", "F"]
    }
}

 

 

✅ 요약

	DFS	BFS
동작 원리	스택	큐
구현 방법	재귀 함수 이용	큐 자료구조 이용

 

코딩 테스트 중 2차원 배열에서의 탐색 문제를 만나면 이렇게 그래프 형태로 바꿔서 생각하면 좋다.

 

 

✅ 음료수 얼려 먹기

 

와 이거 생각보다 어려웠다. 이게 DFS구나!! 머리속으로는 이렇게 설계해야 한다는 생각은 드는데 이걸 코드로 바꾸려니까 상당히 어려웠다.

하나의 포인트에서 상하좌우를 모두 호출한다. 방문한 노드를 1로 바꾸는데, 이건 코드를 보면 이해가 가는데 내가 이렇게 설계하고 풀 수 있을지 모르겠다.

 

 

✅ 미로 탈출

 

미로 탈출의 경우에는 시작지점에서 가까운 곳을 찾으면 되므로 BFS로 이동한다. 여기 문제에서는 우측 하단으로 이동한다. 어려웠는데, 아무튼 비슷한 문제를 찾아보자