BFS(너비우선탐색), DFS(깊이우선탐색)

# BaaarkingDog 님의 강의를 참고했습니다

 

BFS

다차원 배열에서 각 칸을 방문할 때, 너비를 우선으로 방문하는 알고리즘

 

 

STL container의 pair 기능을 사용해 좌표 입력

pair <int, int> t2 = { 4,6 }; // C++ 11

 

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second 
// pair에서 first, second를 줄여서 쓰기 위해서 사용
// t.first, t.second 대신 t.X, t.Y로 사용 가능
int board[502][502] =
{ 
 {1,1,1,0,1,0,0,0,0,0},
 {1,0,0,0,1,0,0,0,0,0},
 {1,1,1,0,1,0,0,0,0,0},
 {1,1,0,0,1,0,0,0,0,0},
 {0,1,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0} }; // 1이 파란 칸, 0이 빨간 칸에 대응
bool vis[502][502]; // 해당 칸을 방문했는지 여부를 저장
int n = 7, m = 10; // n = 행의 수, m = 열의 수
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 }; // 상하좌우 네 방향을 의미

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    queue<pair<int, int> > Q;
    vis[0][0] = 1; // (0, 0)을 방문했다고 명시
    Q.push({ 0,0 }); // 큐에 시작점인 (0, 0)을 삽입.
    while (!Q.empty()) {
        pair<int, int> cur = Q.front(); Q.pop();
        cout << '(' << cur.X << ", " << cur.Y << ") -> ";
        for (int dir = 0; dir < 4; dir++) { // 상하좌우 칸을 살펴볼 것이다.
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir]; // nx, ny에 dir에서 정한 방향의 인접한 칸의 좌표가 들어감
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 범위 밖일 경우 넘어감
            if (vis[nx][ny] || board[nx][ny] != 1) continue; // 이미 방문한 칸이거나 파란 칸이 아닐 경우
            vis[nx][ny] = 1; // (nx, ny)를 방문했다고 명시
            Q.push({ nx,ny });
        }
    }
}

<출처: 바킹독의 실전 알고리즘 강의> https://www.youtube.com/watch?v=ftOmGdm95XI&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=10

 

[포인트]

1. 시작점에 방문했다는 표시를 놓치지 않아야 함

2. 큐에 넣었을 때 체크를 해야 함 (뺄 때 체크 X)

3. 이웃한 원소가 범위를 벗어났는지에 대해 체크

4. ** 거리 잴 때 알고리즘을 의심하지 말 것 **

 

 

DFS

다차원 배열에서 각 칸을 방문할 때, 깊이 우선으로 방문하는 알고리즘

 

** BFS에서 큐만 스택으로 바꿈

 

BFS vs DFS

BFS

- 거리순으로 방문

- 거리를 잴 수 있음

 

DFS

- 한 방향으로 파다가 막히면 다른 점에서 다시 출발

- 거리를 잴 수 없음

 

다차원 배열에서 BFS 사용

그래프와 트리에서 DFS 사용