[알고리즘] DFS/ BFS

탐색(Search): 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

• 그래프, 트리 등의 자료구조 안에서 탐색하는 문제를 주로 다룬다.
• 대표적인 탐색 알고리즘으로 DFS와 BFS가 있다.

 

두 알고리즘을 이해하기 위해 필요한 자료구조

자료구조(Data Struture): 데이터를 표현하고 관리하고 처리하기 위한 구조

 

스택과 큐는 자료구조의 기초 개념으로 다음 두  핵심 함수로 구성된다.

• 삽입(Push): 데이터를 삽입
• 삭제(Pop): 데이터를 삭제

오버플로우(Overflow): 특정 자료구조가 수용할 수 있는 데이터의 크기를 넘은 상태에서 삽입 연산을 수행할 때 발생

언더플로우(Underflow): 특정 자료구조에 데이터가 들어있지 않은 상태에서 삭제 연산 수행 시 발생

 

스택(Stack): 데이터를 들어온 순서대로 쌓고 가장 마지막으로 들어온 데이터부터 나가는 구조, 선입 후출(FILO) 구조 또는 후입 선출(LIFO) 구조라고 한다.

큐(Queue): 가장 먼저 들어온 데이터부터 나가는 구조, 선입선출(FIFO) 구조라고 한다.

 

재귀 함수(Recursive Function): 자기 자신을 다시 호출하는 함수, 무한대로 재귀 호출 시 오류가 발생하기 때문에 종료 조건 명시가 필요하다. 간결하게 코드를 작성할 수 있다.

 

 

그래프: 노드(Node)와 간선(Edge)으로 표현된다. 두 노드가 간선으로 연결되어 있으면 두 노드는 인접하다고 표현

그래프 탐색: 하나의 노드를 시작으로 다수의 노드를 방문

• 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현하는 방식
• 인접 리스트(Adjacency List): 리스트로 그래프 연결 관계를 표현하는 방식
• 메모리 측면에서 인접 행렬을 노드의 개수가 많을수록 메모리 낭비, 인접 리스트 방식은 효율적
• 인접 리스트 방식은 인접 행렬 방식에 비해 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느림

 

DFS(Depth-First Search)

• 깊이 우선 탐색
• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 특정한 경로로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후 다시 돌아가 다른 경로를 탐색하는 알고리즘
• 모든 노드를 방문하고자 하는 경우에 사용
• BFS에 비해 간단하지만, BFS에 비해 느림
• 스택 또는 재귀 함수를 이용하여 구현

DFS 동작 과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없다면 최상단 노드를 꺼낸다
3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

BFS(Breadth First Search)

• 너비 우선 탐색
• 가까운 노드부터 탐색하는 알고리즘
• 두 노드 사이의 최단 경로를 찾을 때 사용
• 큐를 이용하여 구현

BFS 동작 과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 오드를 모두 큐에 삽입하고 방문 처리한다.
3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

 

DFS와 BFS의 시간 복잡도

• 두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도 동일
• 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간의 합
• 인접 리스트: O(N+E)
• 인접 행렬: O(N²)

 

DFS와 BFS 문제 유형

• 그래프의 모든 노드를 방문하는 것이 중요한 문제 => DFS, BFS
• 경로의 특징을 저장해둬야 하는 문제 => DFS
• 최단거리를 구해야 하는 문제 => BFS

 

---

DFS / BFS 문제

음료수 얼려 먹기

N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.
구명이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.
이때, 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.

var input = readLine()!.split(separator: " ").map{Int(String($0))!}
var n = input[0], m = input[1]

var graph = [[Int]]()

for i in 0..<n{
    graph.append(readLine()!.map{Int(String($0))!})
}

func dfs(_ x: Int, _ y: Int) -> Bool{
    if x <= -1 || x >= n || y <= -1 || y >= m {
        return false
    }
    
    if graph[x][y] == 0{
        graph[x][y] = 1
        
        dfs(x-1, y)
        dfs(x, y-1)
        dfs(x+1, y)
        dfs(x, y+1)
        return true
    }
    return false
}

var result = 0

for i in 0..<n{
    for j in 0..<m{
        if dfs(i,j) == true{
            result += 1
        }
    }
}

print(result)

---

미로 탈출

동빈이는 N x M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 괴물들이 있어 이를 피해 탈출해야 한다.
동빈이는 (1,1)에, 출구는 (N, M)에 존재하며, 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0, 없는 부분은 1로 표시된다.
미로는 반드시 탈출할 수 있는 형태로 제시될 때, 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오.

//swift는 큐를 제공하지 않아 직접 구현
struct Queue<T> {
    private var queue: [T] = []
    
    public var count: Int {
        return queue.count
    }
    
    public var isEmpty: Bool {
        return queue.isEmpty
    }
    
    public mutating func enqueue(_ element: T) {
        queue.append(element)
    }
    
    public mutating func dequeue() -> T? {
        return isEmpty ? nil : queue.removeFirst()
    }
}


var input = readLine()!.split(separator: " ").map{Int(String($0))!}
var n = input[0], m = input[1]

var graph = [[Int]]()

for i in 0..<n{
    graph.append(readLine()!.map{Int(String($0))!})
}

var dx = [-1, 1, 0, 0]
var dy = [0, 0, -1, 1]

func bfs(_ x: Int, _ y: Int) -> Int{
    var queue = Queue<(Int,Int)>()
    queue.enqueue((x,y))
    
    while !queue.isEmpty{
        var (x,y) = queue.dequeue()!
        
        for i in 0..<4{
            var nx = x + dx[i]
            var ny = y + dy[i]
            
            if nx < 0 || ny < 0 || nx >= n || ny >= m{ continue }
            if graph[nx][ny] == 0{continue}
            if graph[nx][ny] == 1 {
                graph[nx][ny] = graph[x][y] + 1
                queue.enqueue((nx,ny))
            }
        }
        
    }
    return graph[n-1][m-1]
}
print(bfs(0, 0))