DFS

DFS란 무엇인가?

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

 

문제풀이에서 DFS의 활용방식은?

-Flood-Fill

-그래프 트리 탐색에서 활용

 

BFS vs DFS(방문 순서)

STL

#define X first
#define Y second
int board[512][512];
bool vis[512][512];
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);
    stack<pair<int,int>> s;
    vis[0][0] = 1;
    s.push({0,0});
    while(!s.empty()){
        pair<int,int> cur = s.top(); s.pop();
        for(int dir=0; dir<4; dir++){
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue();
            if(vis[nx][ny] || board[nx][ny] != 1) continue();
            vis[nx][ny] = 1;
            s.push({nx,ny});
        }
    }
}