[알고리즘 정리] DFS

DFS

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

BFS

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

1. 시작하는 칸을 스택에 넣고 방문했다는 표시를 남김
2. 스택에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해 3번을 진행
3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입
4. 스택이 빌 때까지 2번을 반복

stack<pair<int, int>> s;
vis[0][0] = 1;
s.push({0, 0});
while(!s.empty()){
	tie(y, x) = s.front(); s.pop();
    for(int i = 0 ;i < 4; i++){
    	int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny < 0 ~ ) continue;
        if(vis ~) continue;
        vis[ny][nx] = 1;
        s.push({ny, nx});
    }
}

굳이 BFS말고 DFS 로 푸는 문제는 따로 없다.