[알고리즘] 너비 우선 탐색(BFS)

한은기·2022년 2월 19일

Data Structure & Algorithm

목록 보기

9/10

1. 너비 우선 탐색

너비 우선 탐색(Breath-First Search, BFS)는 출발 지점으로부터 가까운 순서대로 방문하는 탐색법이다. 트리를 기준으로 본다면 한 수준(level)의 방문이 끝나야 다음 수준의 노드를 방문하며, 그래프 기준으로 본다면 출발지로부터 간선 개수가 적은 노드들부터 우선 방문하는 것이다.

BFS는 큐로 구현할 수 있다. 큐에 든 노드들을 하나하나 꺼내 방문한다. 각 노드 방문 시에는 방문하고 있는 노드들로부터 가장 가까운 노드들을 큐에 넣는다. 트리에서 보자면 자기 자식들을, 그래프에서 보자면 간선 하나를 거쳐 갈 수 있는 노드들을 넣는 셈이다. 큐를 사용하는 이유는 선입선출의 원리를 적용하기 때문으로, 가장 먼저 넣은 노드들부터 방문하게 되므로 최종적으로는 한 수준(level)이 끝났을 때 큐 안에는 다음 수준들의 노드가 나열되어 있을 것이다. 즉 다음에 방문해야 할 노드들 순서가 완성되어 있을 것이다.

이렇게 같은 수준(거리)의 노드를 먼저 탐색하므로 가로를 우선 탐색하여 '너비'우선 탐색이라고 한다. 세로로 깊게 파는 '깊이' 우선 탐색(DFS)과는 다르다. DFS는 여러 용도로 쓰일 수 있으나, BFS는 거의 최단 거리 길찾기에만 쓰인다. 그러나 이 때 역시 제한사항은 있는데, 모든 노드가 가중치 없이 동등해야 하며 상하좌우가 아닌 대각선 이동의 경우 가중치가 $\sqrt{2}$ 만큼 곱해지므로 불가하다. 트리를 생각해보면 간선의 길이가 들쭉날쭉 길어지는 것이 되어 어디가 어떤 레벨인지 파악하기 힘들기 때문이다. 따라서 가중치가 있는 그래프는 '다익스트라 최단 경로 알고리즘'을 이용해 찾아야 한다.

2. 예시 문제

코드를 참고한 곳은 하단 참고링크에 표시해두었다.

2-1. 게임 맵 최단거리 (프로그래머스)

👉 문제 링크
🔍 풀이 방식
각 길마다 가중치가 존재하지 않는다. BFS를 이용해 풀면 도착지까지 최단거리는 다른 노드들의 최단거리로 구할 수 있다. 큐를 사용하므로 출발지로부터 거리 순으로 방문된다.

#include <vector>
#include <queue>

using namespace std;

// 좌표를 저장할 클래스. x, y를 담고 있다.
class Coord {
public:
    int x;
    int y;

    Coord(int _x, int _y) {
        x = _x;
        y = _y;
    }
};

int solution(vector<vector<int> > maps)
{
    int n = maps.size();  // 게임맵의 세로 길이
    int m = maps[0].size(); // 게임 맵의 가로 길이

    vector<vector<int>> dist(n, vector<int>(m)); // (y,x) 위치까지 오는데 걸리는 거리를 저장할 벡터
    vector<vector<bool>> visited(n, vector<bool>(m)); // (y, x) 위치를 방문했는지 저장할 벡터
    queue<Coord> q;  // 앞으로 방문해야 할 곳을 담는 큐

    //// 움직일 방향. 상-우-하-좌 순서로 방문한다.
    int dx[] = { 0, 1, 0, -1 };
    int dy[] = { 1, 0, -1, 0 };

    //// 시작점을 큐에 담고 그곳의 위치를 1로 하며 방문 여부를 기록한다.
    q.push(Coord(0, 0));
    dist[0][0] = 1;
    visited[0][0] = true;

    //// 큐가 빌 때까지 반복한다
    while (!q.empty())
    {
        Coord cur = q.front();  // 큐의 가장 앞쪽 원소를 현재 위치로 한다.
        q.pop();  // 그곳을 기준으로 이제 탐색할 것이므로 현재 위치는 큐에서 제거한다.
        int curX = cur.x;  // 현재 위치의 x 좌표
        int curY = cur.y;  // 현재 위치의 y 좌표

        //// 상-우-하-좌 순서로 4방향을 탐색한다.
        for (int i = 0; i < 4; i++)
        {
            int nxtX = curX + dx[i];  // 다음 위치의 x 좌표
            int nxtY = curY + dy[i];  // 다음 위치의 y 좌표

            if (nxtX < 0 || nxtX >= m || nxtY < 0 || nxtY >= n)
                continue;  // 다음 위치가 맵을 벗어나면 취급하지 않는다.
            if (maps[nxtY][nxtX] == 0)
                continue;  // 다음 위치가 벽이라면 취급하지 않는다.
            if (visited[nxtY][nxtX])
                continue;  // 다음 위치가 이미 방문한 곳이라면 취급하지 않는다

            q.push(Coord(nxtX, nxtY));  // 다음 위치는 갈 수 있는 곳이므로 큐에 넣는다.
            visited[nxtY][nxtX] = true;  // 다음 위치를 방문했다고 표시한다.
            dist[nxtY][nxtX] = dist[curY][curX] + 1;  // 현재 위치에서 다음 위치까지는 1이 걸리므로 다음 위치의 dist에 1을 더해 표시한다.
        }
    }

    if (!visited[n - 1][m - 1])
        return -1;  // 목적지를 방문한 적이 없으면 그곳까지 도달할 수 없다는 뜻이므로 -1 반환
    else
        return dist[n - 1][m - 1];  // 목적지의 dist가 그곳까지의 최단거리이다.
}

2-2. 카드 짝 맞추기 (프로그래머스)

👉 문제 링크
🔍 풀이 방식
카드 종류 중 무엇을 먼저 방문해야 할지 순서를 정해야 한다. 따라서 순열로 카드 방문 순서의 경우의 수를 모두 구한 뒤 순차적으로 따져본다.
한 칸만 이동하는 것이 아니라 [ctrl]을 누르고 방문했을 때의 위치도 추가적으로 구해 큐에 담아야 한다.

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector<vector<int>> b;  // 한 카드 순서 경우를 탐색할 때마다 board의 초깃값을 다시 받아올 보드
int row;  // 원하는 카드 탐색을 시작할 행 위치
int col;  // 원하는 카드 탐색을 시작할 열 위치
int answer = INT16_MAX;  // 최솟값을 찾아야 하므로 일단 가장 큰 값으로 초기화

//// 움직일 방향. 하-우-상-좌 순으로 움직인다.
int dc[] = { 0, 1, 0, -1 };
int dr[] = { 1, 0, -1, 0 };


int bfs(int cardNum)
{
    bool visited[4][4] = { 0, };  // 그 위치를 방문했는지를 나타낼 배열
    queue<pair<pair<int, int>, int>> q; // < <r, c>, 횟수 >로 큐에 저장된다.

    q.push({ { row, col }, 0 });  // 초기 위치를 큐에 넣는다.
    visited[row][col] = true;  // 초기 위치의 방문 여부를 표시한다.

    //// 큐가 빌 때까지 탐색한다.
    while (!q.empty())
    {
        /* 1. 현재 위치 갱신 */
        int curR = q.front().first.first;  // 큐의 맨 앞 위치의 행 값
        int curC = q.front().first.second;  // 큐의 맨 앞 위치의 열 값
        int cnt = q.front().second; // 큐의 맨 앞 위치까지 걸리는 횟수
        q.pop();
        
        /* 2. pop한 곳이 내가 찾으려는 카드인 경우, 커서 위치 업데이트하고 리턴 */
        if (b[curR][curC] == cardNum)
        {
            b[curR][curC] = 0;  // 카드를 뒤집었으므로 없는 카드 처리한다.
            row = curR;  // 커서 행 위치를 현재 위치로 한다.
            col = curC;  // 커서 열 위치를 현재 위치로 한다.
            return cnt + 1;  // [Enter] 키에도 한 번이 소요되므로 1을 더해 리턴한다.
        }
        
        /* 3. 한 칸 이동한 곳 */
        for (int i = 0; i < 4; i++)
        {
            int nxtR = curR + dr[i];  // 다음 위치의 열 
            int nxtC = curC + dc[i];  // 다음 위치의 행

            if (nxtR < 0 || nxtR >= 4 || nxtC < 0 || nxtC >= 4)
                continue;  // 맵을 벗어났을 경우 취급하지 않는다.
            if (visited[nxtR][nxtC])
                continue;  // 이미 그 위치를 방문했을 경우 취급하지 않는다.

            q.push({ {nxtR, nxtC}, cnt + 1 });  // 다음 위치의 행&렬 값과 그곳까지 [화살표키]를 눌러야 하므로 횟수에 1 추가해 큐에 넣는다.
            visited[nxtR][nxtC] = true;  // 다음 위치를 방문 표시한다.
        }

        /* 4. ctrl 누르고 이동한 곳 */
        for (int i = 0; i < 4; i++)
        {
            int nxtR = curR;  // 다음 위치를 일단 현재 위치로 한다.
            int nxtC = curC;

            // 다음 위치가 맵을 벗어나지 않을 때까지 위치를 1씩 더해 반복하며 [ctrl] 했을 때 위치를 구한다.
            while (nxtR + dr[i] >= 0 && nxtC + dc[i] >= 0 && nxtR + dr[i] < 4 && nxtC + dc[i] < 4)
            {
                nxtR += dr[i];
                nxtC += dc[i];
                if (b[nxtR][nxtC])
                    break; // 한 칸씩 증가시켜가는 도중에 (어느 종류든) 카드를 만난다면 멈춤
            }

            if (visited[nxtR][nxtC])
                continue;  // [ctrl] 하고 움직인 곳이 방문한 곳이라면 취급하지 않는다.

            q.push({ {nxtR, nxtC}, cnt + 1 });
            visited[nxtR][nxtC] = true;
        }
    }
}

int solution(vector<vector<int>> board, int r, int c) {
    /* 1. 존재하는 카드 종류 파악하기 */
    bool cardsExist[7] = { 0, }; // 입력으로는 1~6까지 7개의 종류가 주어진다.
    for (int i = 0; i < board.size(); i++)
    {
        for (int j = 0; j < board[0].size(); j++)
        {
            if (board[i][j])
                cardsExist[board[i][j]] = true;  // 카드 종류가 2, 5, 6이 있다고 하면 그 숫자에만 true 표시를 함. 그 종류가 있다는 뜻.
        }
    }

    /* 2. 오름차순으로, 존재하는 카드 벡터 만들기 */
    vector<int> cards;
    for (int i = 1; i < 7; i++)
        if (cardsExist[i])
            cards.push_back(i);  // 카드가 존재할 때만 그 숫자를 넣는다.

    /* 3. 순열로 방문할 카드의 순서를 정하고, BFS로 횟수 구하기 */
    do
    {
        //// 보드 상태와 시작 위치를 초기화한다
        b = board;
        row = r;
        col = c;

        int cntTemp = 0;  // 카드 짝을 맞추는 데 필요한 이동 횟수

        for (int card : cards)  // 맞춰야 하는 카드의 순서대로 목표 카드를 정한다.
        {
            cntTemp += bfs(card);  // 두 개 중 한 카드를 여는 데 필요한 이동 횟수
            cntTemp += bfs(card);  // 나머지 하나를 여는 데 필요한 이동 횟수
        }

        answer = min(answer, cntTemp);  
            // 모든 카드 순서의 경우의 수를 따지므로, 해당 카드 방문 순서에서의 방문 값이 최소라면 그것으로 업데이트
    } while (next_permutation(cards.begin(), cards.end()));

    return answer;
}

2-3. 경주로 건설 (프로그래머스)

👉 문제 링크
🔍 풀이 방식
이전 문제들과는 다르게 한 번 탐색했던 점을 다시 탐색해야 한다. 또한 그 점까지 오는 방향(dir)도 알고 있어야 한다. 때문에 특정 위치에서의 비용을 저장할 cost 벡터를 3차원으로 선언해 상하좌우 이동 각각에 대해 또 다시 상하좌우 방향에서의 비용을 계산했다.
참고했던 블로그를 보면 BFS 뿐만 아니라 다익스트라, DFS로도 풀리는 문제였다.

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3

// 각 점의 위치와 비용, 방향을 저장할 구조체
struct Pos {
    int y, x, cost, dir;
};

int solution(vector<vector<int>> board) {
    int n = board.size();
    int dy[] = { -1, 1, 0, 0 };
    int dx[] = { 0, 0, -1, 1 };

    vector<vector<vector<int>>> cost(25, vector<vector<int>>(25, vector<int>(4, 999999)));
        // 각 위치와 각 방향에서의 비용을 저장할 3차원 벡터. 
        // 최소 비용을 구해야 하므로 큰 값으로 모두 초기화 해둔다.
    for (int i = 0; i < 4; ++i)
        cost[0][0][i] = 0;  // 첫 번째 점은 비용을 0으로 한다.

    queue<Pos> q;  // 큐를 생성한다.
    q.push({ 0, 0, 0, -1 });  // 맨 첫 점의 방향은 그 어떤 곳도 아닌 -1로 하여 큐에 넣는다.

    while (!q.empty()) 
    {
        Pos cur = q.front();
        q.pop();

        for (int i = 0; i < 4; ++i) 
        {
            int nextY = cur.y + dy[i];
            int nextX = cur.x + dx[i];
            int nextDir = i;  // 상하좌우 탐색할 방향
            int nextCost = cur.cost;

            if (nextY < 0 || nextY >= n || nextX < 0 || nextX >= n || board[nextY][nextX] == 1)
                continue;  // 다음 위치가 맵을 벗어난다면 취급하지 않는다.

            nextCost += 100;  // 특정 점까지 오는 데 코너든 아니든 무조건 직선 도로는 하나 필요하므로 100을 더해놓는다.

            //// 현재 점까지 오는 방향과 지금의 방향을 고려했을 때 코너가 필요하다면 500원을 더한다.
            if ((cur.dir == UP || cur.dir == DOWN) && (nextDir == LEFT || nextDir == RIGHT))
                nextCost += 500;
            if ((cur.dir == LEFT || cur.dir == RIGHT) && (nextDir == UP || nextDir == DOWN))
                nextCost += 500;

            if (nextCost < cost[nextY][nextX][nextDir]) 
            { 
                // 지금 계산한 값이 최소비용이라면 업데이트하고 큐에 넣는다.
                cost[nextY][nextX][nextDir] = nextCost;
                q.push({ nextY, nextX, nextCost, nextDir });
            }
        }
    }

    int answer = cost[n - 1][n - 1][0];
    for (int i = 1; i < 4; i++)
        answer = min(cost[n - 1][n - 1][i], answer);  // 네 방향 중 가장 작은 비용을 찾아 답으로 한다.
    return answer;
}



/*
아래의 풀이는 시간초과가 난 풀이.

특정 위치에 이전 점의 위치를 포함해 저장했으며, 
'이전 위치 ~ 현재 위치 ~ 다음 위치'가 일직선인지 아닌지에 따라 코너 여부를 파악함
방문했던 곳을 다시 방문할 수 있으므로 큐에는 같은 위치가 저장되더라도 '이전 점의 위치'가 다를 수 있음.
*/
/*
struct Pos
{
    int r;
    int c;
    int preR;
    int preC;
    Pos(int _r, int _c, int _preR, int _preC) { r = _r; c = _c; preR = _preR; preC = _preC; }
};

int solution(vector<vector<int>> board) {
    int rowSize = board.size();
    int colSize = board[0].size();

    vector<vector<int>> cost(rowSize, vector<int>(colSize, INT16_MAX));
    queue<Pos> nxtQ;

    int dc[] = { 0, 1, 0, -1 };
    int dr[] = { 1, 0, -1, 0 };

    nxtQ.push(Pos(1, 0, 0, 0));
    nxtQ.push(Pos(0, 1, 0, 0));

    cost[0][1] = 100;
    cost[1][0] = 100;

    while (!nxtQ.empty())
    {
        Pos cur = nxtQ.front();
        int curR = cur.r;
        int curC = cur.c;
        int preR = cur.preR;
        int preC = cur.preC;
        nxtQ.pop();

        for (int i = 0; i < 4; i++)
        {
            int nxtR = curR + dr[i];
            int nxtC = curC + dc[i];

            if (nxtR < 0 || nxtR >= rowSize || nxtC < 0 || nxtC >= colSize)
                continue;
            if (nxtR == preR && nxtC == preC)
                continue;
            if (board[nxtR][nxtC] == 1)
                continue;

            nxtQ.push(Pos(nxtR, nxtC, curR, curC));

            int newCost;
            if ((preR == curR && curR == nxtR) || (preC == curC && curC == nxtC))
                newCost = cost[curR][curC] + 100;
            else
                newCost = cost[nxtR][nxtC] = cost[curR][curC] + 600;

            cost[nxtR][nxtC] = min(cost[nxtR][nxtC], newCost);
        }
    }

    return cost[rowSize - 1][colSize - 1];
}
*/

참고자료

한은기

🏫Inha Univ. Naval Architecture and Ocean Engineering & Computer Engineering (Undergraduate) / 🚢Autonomous Vehicles, 💡Machine Learning