BFS와 DFS

void BFS(int x, int y){
    deque<pair<int, int>> dq;
    dq.push_back({x,y});
    
    while(!dq.empty(){
    	x = dq.front().first;
        y = dq.front().second;
        dq.pop_front();
    	for(int i=0; i<4; i++) {
            int nx = x + dr[i];
            int ny = y + du[i];
        
            if(방문체크)
            else 조건에 모두 부합하면
        }
    }
}

 

 

queue를 대신해 deque를 사용했다. 위의 문제는 전형적인 그래프 탐색 문제인 미로 탈출 유형의 문제이다. 우선 시작점의 좌표를 매개변수로 넣어준다. 이를 deque에 넣고 시작한다. 

 

조건은 deque라는 통 안이 모두 빌 때까지가 기본이며, 문제에 따라 여러 종료조건이 붙기도 한다.

 

미로탐색에서 위, 아래, 왼쪽, 오른쪽으로 이동할 수 있는 문제라 가정한다면 for문을 각 위치(x,y)에 따라 4번씩 돌려야 한다. 즉 nx, ny는 x, y에서 위, 아래, 왼쪽, 오른쪽으로 각각 이동했을 때의 경우를 나타낸 것이다.

 

nx, ny가 조건에 부합한다면 nx, ny로 이동했을 경우도 넣어주어야 하므로 deque에 push해준다.

 

BFS, DFS 관련 문제는 보통 NxN 배열에서 길을 찾는 문제, 또는 stack과 queue를 이용하여 거리나 촌 수 등을 계산하는 문제 등에 사용된다.