Swift DFS, BFS

Swift 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"]
    }
}

 

 

요약

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

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

 

 

 

 

1. 음료수 얼려 먹기

 

DFS 기본 문제로 머리속으로는 이렇게 설계해야 한다는 생각은 드는데 이걸 코드로 바꾸려니까 상당히 어려웠음.

하나의 포인트에서 상하좌우를 모두 호출.

시뮬레이션도 섞였는데, 그냥 천천히 집중해서 풀면 됨.

 

 

2. 미로 탈출

 

미로 탈출의 경우에는 시작지점에서 가까운 곳을 찾으면 되므로 BFS로 이동.

시뮬레이션도 섞였는데, 그냥 천천히 집중해서 풀면 됨.