[나만 몰랐던 알고리즘] 2D 맵 BFS

Breadth-First-Search. 넓이 우선 탐색이다. 2D 맵 나오고 뭐 최단거리 찾아라 이런 문제에 접근 방식을 잘 모르겠어서 찾아보던 와중, 그런 문제는 BFS로 탐색하면 좋다고 해서 알아보았다.

 

문제 뿐만이 아니라 2D 맵 탐색에 막연한 두려움을 가지고 있어 한번 정리해 보았다.

 

맵은 2차원 int 배열로 만든다. 탐색을 할 때, 방문한지 여부를 visited 배열에 저장한다. 이 visited 배열은 문제마다 다를 수 있지만, 대개 map 크기와 같다. BFS 의 탐색 특징은 FIFO(First In First Out)이다. queue를 사용해 방문과정을 탐색한다.

 

현재 상황이나 위치를 구조체로 정의해두면 편하다.

탐색을 할 때 사용할 4방위(상하좌우)나 8방위(상하좌우, 좌상 우상 좌하 우하) 를 전역변수로 미리 선언해두고 쓰면 좋다.

 

visited 배열은 전부 0으로 초기화한다.

탐색 시작 전, 시작 위치를 큐에 넣어주고 visited 배열에도 표시를 해 준다.

 

BFS 의 탐색은 다음과 같은 방식으로 이루어진다.

1. 큐에서 꺼내옴
2. 꺼내온게 목적지인가?
3. 갈 수 있는곳을 순회하며
4. 그곳이 갈 수 있는가?
5. 있으면 방문 체크 후 큐에 넣기!

코드를 보면 이해하기 좋다.

#include <iostream>
#include <string>
#include <queue>
#include <string.h>

// 탐색할 4방위를 전역으로 선언해두면 편하다.
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

// 현재 상황이나 위치를 구조체로 정의해두면 편하다.
typedef struct point
{
    int x;
    int y;
    int cost;
    point(int y, int x, int cost) : x(x), y(y), cost(cost) {}
} point;


int main()
{
    int N, M;
    std::cin >> N >> M;
    int map[N][M]; //지도
    int visited[N][M]; //방문여부 체크

    memset(visited, 0, sizeof(visited));
    for (int i = 0; i < N; i++)
    {
        std::string inp;
        std::cin >> inp;
        for (int j = 0; j < M; j++)
            map[i][j] = inp[j] - '0';
    }

    // for (int i = 0; i < N ; i++)
    // {
    //     for (int j = 0; j < M; j++)
    //         std::cout << map[i][j];
    //     std::cout << "\n";
    // }

    std::queue<point> q;

    q.push(point(0, 0, 1));
    visited[0][0] = 1;
    while(1)
    {
        point cur = q.front();  //1. 큐에서 꺼내옴
        q.pop();
        if (cur.x == M - 1 && cur.y == N - 1) // 2. 꺼내온게 목적지인가?
        {
            std::cout << cur.cost;
            break;
        }
        for (int i = 0; i < 4; i ++) //3. 갈 수 있는곳을 순회하며
        {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];

            if (nx < 0 || nx >= M || ny < 0 || ny >= N || visited[ny][nx] || !map[ny][nx]) //4. 그 곳이 갈 수 있는가?
                continue;
            else
            {
                visited[ny][nx] = 1; //5. 갈 수 있으면 체크
                q.push(point(ny, nx, cur.cost+1)); // 큐에 넣기
            }
        }
    }
}

 

다른 문제의 경우, 물이 홍수가 나듯 퍼지고, 그 와중 탐색해 목적지까지 갈 수 있는지 보는 문제가 있었다. 그 문제의 경우, 한 큐에 경로탐색과 물 퍼지는 것을 전부 넣어서 1턴(탐색, 물 퍼짐), 2턴(탐색, 물 퍼짐) 이렇게 돌아가더라.

어떻게 응용하느냐에 따라서 많이 달라질 수 있을 것 같은데, 정확하게 구조를 잘 알고 있으면 어떻게 달라지면 좋을까 라는 질문에 더 노력을 담을 수 있을 것 같다.

 

오늘도 평온한 하루가 되길. 슨민.