DFS&BFS

 

(이코테 2021 강의 몰아보기) 3. DFS & BFS

그래프 알고리즘, 경로를 찾는 문제 시 상황에 맞게 활용

• 탐색(Search)란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말함
• 대표적인 그래프 탐색 알고리즘으로 DFS, BFS가 있음

Stack

• 선입후출(FILO) 구조의 자료구조
• 입구와 출구가 동일한 형태로 스택을 시각화할 수 있음

 

---

DFS(Depth First Search)

루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하는 방법

깊이 우선 탐색이라고도 부르며, 깊은 부분을 우선적으로 탐색하는 알고리즘

스택 & 재귀함수를 이용해 구현 → 모든 경로를 방문해야 할 경우에 사용

그래프의 구성 요소, 사이클, 위상 정렬 등을 찾는데 유용함.

 

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

• DFS 예제 - 재귀함수를 이용해서 표현

func dfs(_ graph: [[Int]], _ startNode: Int, _ visited: inout [Bool]){
    // 현재 노드를 방문 처리
    visited[startNode] = true
    print(startNode, terminator: " ")
    // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for nextNode in graph[startNode] {
        if !visited[nextNode] {
            dfs(graph, nextNode, &visited)
        }
    }
}

# 2차원 리스트로 노드가 연결된 정보 표현
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

var visited = [Bool](repeating: false, count: graph.count)

dfs(graph, 1, &visited)

DFS, BFS 탐색 순서

---

BFS(Breath First Search)

루트 노드 또는 임의 노드에서 인접한 노드부터 먼저 탐색하는 방법

너비를 우선으로하여 탐색을 수행하는 탐색 알고리즘

너비 우선 탐색이라고도 부르며, 가까운 노드부터 우선적으로 탐색하는 알고리즘

• ‘최단 경로’를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용됨.

ex - 미로 찾기

큐를 통해 구현함. (FIFO)

• 최소 비용이 우선일 때 적합

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

• BFS 예제

// BFS 메서드 정의
func bfs(_ graph: [[Int]], _ startNode: Int, _ visited: inout [Bool]){
    var queue = [Int]()
    queue.append(startNode)
    
    // 큐가 빌 때까지 반복
    while !queue.isEmpty {
        // 큐에서 하나의 원소를 뽑아 
        let node = queue.removeFirst()
        // 만약 이 노드가 아직 방문하지 않았다면 출력 후 방문 처리
        if !visited[node] {
            print(node, terminator: " ")
            visited[node] = true
            // 해당 노드의 방문하지 않은 인접 노드들을 큐에 추가
            for neighbor in graph[node] {
                queue.append(neighbor)
            }
        }
    }
}

// 2차원 리스트로 노드가 연결된 정보 표현
let graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

var visited = [Bool](repeating: false, count: graph.count)

dfs(graph, 1, &visited)

DFS & BFS 기초 문제 풀이

백준 1260번(DFS와 BFS)

import Foundation

// 정점 개수: N, 간선 개수: M, 탐색 시작 정점 번호: V

// 초기값 세팅
let input = readLine()!.split(separator: " ").map{ Int(String($0))!}

let N = input[0]
let M = input[1]
let V = input[2]

var edgeInfo: [Int: Array<Int>] = [:]
var visited: [Bool] = Array(repeating: false, count: N + 1)

var answer = ""

// 그래프 edge 정보 setup
//for _ in 0..<M {
//    let nodeInfo = readLine()!.split(separator: " ").map{ Int(String($0))!}
//    
//    if var array = edgeInfo[nodeInfo[0]] {
//        array.append(nodeInfo[1])
//        edgeInfo[nodeInfo[0]] = array
//    } else {
//        edgeInfo[nodeInfo[0]] = [nodeInfo[1]]
//    }
//}

var graph : [[Int]] = Array(repeating: [], count: N+1)

for _ in 0..<M {
    let relation = readLine()!.split(separator: " ").map{Int(String($0))!}
    let a = relation[0]
    let b = relation[1]
    graph[a].append(b)
    graph[b].append(a)
    graph[a].sort()
    graph[b].sort()
}

func DFS(node: Int) {
    visited[node] = true
    answer += "\(node) "
    
    for edge in graph[node] {
        if !visited[edge] {
            DFS(node: edge)
        }
    }
}

func BFS(node: Int) {
    // 방문해야 하는 노드
    var needVisited: [Int] = [node]
    // 방문한 노드
    var visited = Set<Int>()
    
    while !needVisited.isEmpty {
        let node = needVisited.removeFirst()
        if !visited.contains(node) {
            visited.insert(node)
            answer += "\(node) "
            needVisited.append(contentsOf: graph[node])
            
        }
    }
}

DFS(node: V)
print(answer)
answer = ""
BFS(node: V)
print(answer)

 

---

 

Swift 알고리즘 : DFS & BFS

Swift 알고리즘 : DFS & BFS

 

[Swift] DFS/BFS란 무엇인가? - 깊이우선탐색과 너비우선탐색 구현 | 마고자비 블로그

[Swift] DFS/BFS란 무엇인가? - 깊이우선탐색과 너비우선탐색 구현 | 마고자비 블로그