[알고리즘 깨알 팁] BFS 짜는 법

알고리즘을 풀면 아주아주 많이 마주치는 것이 바로 이 BFS입니다.

BFS는 최단거리를 찾을때 굉장히 자주쓰이죠!

BFS는 보통 큐를 이용한 방식을 사용합니다!

큐의 가장 앞에 있는 노드를 불러서 다음노드들을 맨 뒤에 놓으면,

결국 먼저왔던 노드들은 먼저 처리되고 나중에 불러진 노드들은 나중에 처리됩니다.

BFS는 이런 특징을 이용해서, 같은 거리에 있는 어떤 지점을 처리한 뒤에 다음 거리에 있는 지점을 탐색할 수 있기 때문에 최단거리로 쓸 수 있는 것이죠!

BFS에서 가장 중요한 것은 무엇일까요!?

바로, 방문 체크를 잘 만들어야 한다는 것입니다!

방문 체크를 잘 못만들면 큐에 들어갔던 값이 또 들어가고.. 또 들어가고... 또 들어가서 메모리가 터져버리거든요!

이렇게.. 무한 루프에서 빠져나올수 없게되죠.

하지만! 만약 방문 체크를 한다면!?

이렇게 편안하게 끝납니다. (초록색이 방문 체크입니다.)

그리고 현재 위치만 체크하기 보다는 다음 위치를 미리 방문 체크를 해 놓는게 좋습니다.

왜냐하면!

이처럼, 현재 위치에만 방문체크를 하게 되면 큐에 중복으로 좌표가 들어올 수 있기 때문입니다!

다음 위치를 방문처리하면 이제 큐에서 나오는 값들은 무조건 한 번 나오게 됩니다.

따라서, 불러지는 노드마다 어떤 처리를 한다고 하면, que에서 pop한 상태에서 하도록 합시다!

예를들면.. 어떤 노드에서 방문할 수 있는 노드들이 가지고 있는 가치의 모든 합을 구한다던가 하는 문제 말이죠!

그럼 이제 BFS를 짜는 간단한 템플릿 코드를 만들어 보겠습니다.

struct COD{int r, c};
 
queue<COD> que;
 
while(!que.empty()){
    COD now = que.front();
    que.pop();
 
    //now를 이용한 적절한 처리
    ...
 
    for(/*다음에 올 노드들 보기*/){
        COD next;
 
        //다음 노드로 올 수 있는 적절한 노드인지 확인합니다.
        //방문에 대한 처리, 인덱스가 주어진 문제 밖으로 나갔는지에 대한 처리 등이 포함됩니다.
        if(...){
            //방문 처리를 합니다.
            ...
            que.push(next);
        }         
    }
}

짜잔! 간단한 템플릿 코드가 완성되었습니다.

큐가 빌 떄까지 처리하고, 현재 노드에서 다음 노드가 어떻게 되는지 반복문을 통해 처리합니다.

그리고, next가 유효하다면 큐에 다음 노드를 넣는 방식이죠!

그럼 이제 방문 처리에 대한 얘기를 해볼까 합니다.

보통, 간단한 bfs 문제는 방문 처리가 맵의 차원과 같습니다.

2차원 맵인 경우에는 visit도 2차원으로 만들죠!

하지만, 예외 적인 경우가 있습니다.

추가적인 정보가 주어지거나,

밟았던 곳도 다시 밟을 수 있는 등!

해당 좌표로 갔는데 서로 다른 경우가 생길 수 있는 것이죠!

이를 처리하기 위한 가장 간단한 방법은 방문 배열의 차원을 늘리는 것입니다.

미로 탈출 문제도 그런 유형의 문제죠!

풀이법은 여기에 있습니다.

같은 좌표로 가도, 마법을 사용할 수 있는 유무에 따라서 다른 경우가 되버리는 경우죠!

그렇지만 방문 배열을 visit[마법 사용][X][Y]로 차원을 늘려버리는 순간 중복은 깔끔하게 사라집니다.

이렇게 중복으로 발판을 밟을 수 있다거나, 추가적인 정보가 있으면 우선 이렇게 생각합시다.

'혹시... 방문 배열의 차원을 늘려서 해당 좌표를 중복으로 가는 경우를 막을 수 있지 않을까!?'

생각보다 많은 경우에 통하는 방법입니다! 잊지마세용

이제, 문제의 목표에 따라서 프로그래밍을 하는 방법을 알려드릴까 합니다.

1 .딱 하나의 목표에 최단 거리로 도착하는 경우!

2. 여러 개의 목표 중 하나에 최단 거리로 도착해서, 해당 지점들에 대해서 적절한 처리를 해야하는 경우!

목표가 하나일 경우에는 찾자마자 바로 return을 해주면 됩니다.

코드로는 다음과 같이 나타낼 수 있습니다.

struct COD{int r, c};
 
queue<COD> que;
 
while(!que.empty()){
    COD now = que.front();
    que.pop();
    
    //now를 이용한 적절한 처리를 합니다.
    ...

    //now가 목표라면
    if(...){
        //목표에 대한 처리 후 반복문을 빠져나옵니다.
        ...
        break;
    }
 
    for(/*다음에 올 노드들 보기*/){
        COD next;
 
        //다음 노드로 올 수 있는 적절한 노드인지 확인합니다.
        //방문에 대한 처리, 인덱스가 주어진 문제 밖으로 나갔는지에 대한 처리 등이 포함됩니다.
        if(...){
            //방문 처리를 합니다.
            ...
            que.push(next);
        }         
    }
}

하지만, 목표가 여러개라면 아직 처리 못한 목표가 큐에 남아있을 수 있습니다.

결국엔 현재 거리를 기억해서, 큐에서 현재 거리와 같은 거리를 가지는 노드들을 처리할때까지 반복문을 진행하는 것이 필요합니다.

여러 방법이 있지만, 저는 현재 거리에 대한 노드가 몇 개 있는지를 먼저 저장하는 방식을 주로 사용합니다.

방법은 간단합니다.

편의상 방문 체크는 생략하겠습니다.

위 그림과 같이 현재 큐 사이즈를 저장하면, 같은 거리에 있는 노드들만 처리할 수 있습니다.

처음에 1개의 노드를 처리하면, 거리가 1인 노드들 4개가 생깁니다.

이제 거리가 1인 노드 4개들을 처리하면, 거리가 2인 노드들 8개를 얻을 수 있습니다.

마찬가지로 큐에서 순서대로 8개를 처리하면, 이제 큐에 남아있는 노드들은 모두 거리가 3인 노드들인 것 입니다!

이를 코드로 정리해봅시다.

struct COD{int r, c};
 
queue<COD> que;
 
//초기 세팅
COD first = ...
 
//first 방문 체크
...
que.push(first);
 
while(que.size()){
    int cnt = que.size();
 
    //노드가 목적지에 도달했는지에 대한 변수
    bool isend = false;
 
    while(cnt--){
        COD now = que.front();
        que.pop();
 
        //now에 대한 처리를 합니다.
        ...
 
        //now가 최종 목적지일 경우 처리후 다음 노드로 넘어갑니다.
        if(...){
            isend = true;
            continue;
        }
 
        //다음 노드들 탐색
        for(...){
            //다음 노드에 대한 처리
            COD next = ...
 
            //다음 노드로 올 수 있는 적절한 노드인지 확인합니다.        
            //방문에 대한 처리, 인덱스가 주어진 문제 밖으로 나갔는지에 대한 처리 등이 포함됩니다.            
            if(...){
                //방문 처리를 합니다.
                ...
 
                que.push(next);
            }
        }
        
    }
    
    //목적지에 도달했으면 반복문을 빠져나옵니다.
    if(isend) break;
    //현재 거리에 대한 처리 후 다음에 대한 처리를 위한 처리를 합니다.
    ...     
 
}

이제 기초적인 BFS문제는 풀 수 있을 겁니다!

이만 팁을 마치겠습니다.

쓰고보니 꺠알팁이 아니군요... 꽤 깁니다..