BFS, DFS 공부

- 재귀함수: 자기 자신 다시 호출
: 종료 조건 반드시 명시. 함수 무한 호출 가능

- DFS(Depth First Search) 
: 깊이 우선 탐색. 깊은 부분 우선적으로 탐색
: 스택 or 재귀함수

- DFS 동작 방식
1. 탐색 시작 노드 스택에 삽입, 방문 처리
2. 스택 최상단 노드에 방문하지 않은 인접한 노드 있으면 해당 노드 스택에 삽입, 방문 표시. 방문하지 않은 인접 노드 없으면 스택에서 최상단 노드 꺼낸다.
3. 더이상 2번 수행할 수 없을 때까지 반복

- 베이스 라인

void dfs(int x){
    vis[x] = true;
    cout<< x << ' ';
    for(int i=0; i<graph[x].size();i++){
        int y=graph[x][i];
        if(!vis[y]) dfs(y);
    }
}

 

- BFS(Breadth First Search)
: 다차원 배열에서 각 칸을 방문할 떄 너비를 우선으로 방문하는 알고리즘

- 알고리즘 동작 방식
1. 시작하는 칸을 큐에 넣고 방문 표시 남김
2. 큐에서 원소를 꺼내 그 칸에 상하좌우로 인접한 칸에 대해 3번 진행
3. 해당 칸을 이전에 방문하지 않은 경우 방문 표시 남기고 해당 칸에 큐를 삽입
4. 큐가 빌 때까지 2번 반복.
--> 모든 칸이 큐에 1번씩 들어가므로 시간 복잡도는 칸이 N개일 때 O(N)

- 베이스 라인

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second 
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;
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}); //큐에 방문지 푸시
    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]; //상하좌우 좌표 계산
            if(nx<0||ny<0||nx>=n||ny>=m) continue;//범위 넘어가는 경우 다음으로
            if(board[nx][ny]!=1 ||vis[nx][ny]==1) continue;//보드에 색칠 안되어있거나, 방문 한경우 다음으로
            vis[nx][ny]=1;// (nx,ny) 방문 표시
            Q.push({nx,ny});//방문지 푸시 후 다시 큐 탐색
        }
    }
}