[알고리즘] 02. BFS와 DFS 알고리즘의 뼈대 with Swift

BFS(너비우선탐색)

1. removeFirst() 사용

func bfs(graph: [[Int]], startX: Int, startY: Int) -> [Int] {
    var visited = Array(repeating: Array(repeating: false, count: n), count: n)
    var queue = [(startX, startY)]
    var result = [Int]()
    
    visited[startX][startY] = true
    
    while let node = queue.isEmpty ? nil : queue.removeFirst() {
        let x = node.0
        let y = node.1
        
        result.append(graph[x][y])
        
        let dx = [0, 0, 1, -1]
        let dy = [1, -1, 0, 0]
        
        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]
            
            if nx < 0 || ny < 0 || nx >= n || ny >= n || visited[nx][ny] {
                continue
            }
            
            visited[nx][ny] = true
            queue.append((nx, ny))
        }
    }
    
    return result
}

 

2. 인덱스로 접근

removeFirst()로 인한 시간초과를 피하려면 인덱스로 큐를 순회할 수도 있다.

백준 문제

var idx = 0

while idx < queue.count {
    let now = queue[idx]
    idx += 1
    
    for i in 0..<N {
        ...
        queue.append(n)
		....
	}
}

 

 

3. 이동 횟수를 카운트해야하는 경우

백준 문제

var queue: [(Int, Int)] = [st]
var nxt_queue: [(Int, Int)] = []

func move() {
    for q in queue {
        for i in 0..<4 {
            let nx = q.0 + dx[i]
            let ny = q.1 + dy[i]
            
            if 0 > nx || nx >= R || 0 > ny || ny >= C {
                success = true
            } else {
                if map[nx][ny] == "#" || map[nx][ny] == "F" || map[nx][ny] == "J" { continue } // 넘어가는 조건
                map[nx][ny] = "J"
                nxt_queue.append((nx, ny))
            }
        }
    }
}

while true {
    nxt_queue = [] // 새로 저장할 큐 초기화

    if queue.isEmpty {
        print("IMPOSSIBLE")
        break
    }
   
    time += 1

    move()
    
    if success {
        print(time)
        break
    }
    queue = nxt_queue // 다음 순회할 큐 만들어주기
}

 

 

DFS(깊이우선탐색)

func dfs(graph: [[Int]], startX: Int, startY: Int) -> [Int] {
    var visited = Array(repeating: Array(repeating: false, count: n), count: n)
    var stack = [(startX, startY)]
    var result = [Int]()
    
    visited[startX][startY] = true
    
    while let node = stack.isEmpty ? nil : stack.removeLast() {
        let x = node.0
        let y = node.1
        
        result.append(graph[x][y])
        
        let dx = [0, 0, 1, -1]
        let dy = [1, -1, 0, 0]
        
        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]
            
            if nx < 0 || ny < 0 || nx >= n || ny >= n || visited[nx][ny] {
                continue
            }
            
            visited[nx][ny] = true
            stack.append((nx, ny))
        }
    }
    
    return result
}

 

 

위의 코드에서 BFS는 큐(Queue)를 사용하여 탐색을 진행하고, DFS는 스택(Stack)을 사용하여 탐색을 진행합니다.

코드에서 큰 차이는 queue.removeFirst(), stack.removeLast()라고 보면 좋을 듯 합니다.

 

BFS는 시작점에서 가까운 노드부터 먼저 탐색하고, 그 다음에 가까운 노드를 탐색하는 방식으로 진행되며,

DFS는 한 노드를 탐색한 후에는 해당 노드의 자식 노드를 먼저 탐색하고, 그 다음에 형제 노드를 탐색하는 방식으로 진행됩니다.

 

BFS는 탐색할 영역이 복잡하거나, 탐색 순서가 중요한 경우에 사용되고, DFS는 탐색할 영역이 간단하거나, 탐색 순서가 중요하지 않은 경우에 사용됩니다.