[컴퓨터 알고리즘] DFS 알고리즘 & BFS 알고리즘

BFS 알고리즘과 DFS 알고리즘의 모습

 사진 출처:    https://velog.io/@vagabondms/DFS-vs-BFS

DFS 알고리즘

---

• 오른쪽 사진에서 볼 수 있듯이, 한 경로를 타고 들어가 그 depth가 끝날 때까지 해가 되는 경로를 찾는 경우이다.
• 한 depth에서의 모든 노드를 저장하는 것이 아니라 한 경로의 node들만 저장하기에 BFS보다 저장할 데이터 양 자체는 적다.
• 허나 발견한 경로가 최단 경로임을 알 수 없고, 해를 찾기 전 접근한 경로의 depth가 무한히 크다면, 해가 있더라도 이를 찾을 수 없다.

 

BFS 알고리즘

---

• 같은 depth의 모든 노드들을 하나씩 지나가면서 탐색하므로, 해를 발견한다면 그 해가 최단 경로임이 분명하다.
• 하지만 큐에 저장해야 할 노드 들이 한 depth의 모든 노드들이므로 해가 나오기 전까지 저장해야 할 노드의 수가 굉장히 많다.

 

아래는 BFS 알고리즘을 사용해 해결한 백준 Gold 수준의 문제이다.

https://baekjoon-deeplearning.tistory.com/24

백준 16928 - 뱀과 사다리 게임 [C/C++] BFS 알고리즘

int game(int start, int c){
    queue<pair<int,int>> q;
    q.push({start,c});
    while (!q.empty()){
        int x = q.front().first;
        int cnt = q.front().second;
        q.pop();
        for (int i=1;i<=6;i++){
            int nx = x+i;
            if (nx >= 100){
                return cnt+1;
            }
            while(board[nx]!=0) nx = board[nx];
            if (visited[nx]) continue;
            visited[nx] = true;
            q.push({nx, cnt+1});
        }
    }
}

 

아래는 백트래킹 알고리즘을 DFS 방식으로 구현해서 문제를 푼 포스팅이다.

https://baekjoon-deeplearning.tistory.com/52

백준 15654 - N과 M (5) [C/C++]

void Permutation(int len){
    if(len==howmany){
        for(int i=0;i<howmany;i++){
            cout << result[i] << " ";
        }
        cout << '\n';
    }
    else{
        for(int i=0;i<num;i++){
            if(check[i]==0){
                result[len] = lst[i];
                check[i] = 1;
                Permutation(len+1);
                check[i] = 0;
            }
        }
    }
}