다차원 배열이 주어졌을 때 Queue를 이용하여 BFS 구현하기 : C++

백준의 문제를 풀다보면 다차원 배열, 즉 여러 개의 칸으로 이루어져 있는 구조가 있고 칸들을 탐색해야 할 때가 있다. 따라서 다차원 배열이 주어졌을 때 queue를 사용하여 BFS를 구현하는 방법에 대해서 알아보겠다. 문제에 맞게 해당 방법을 베이스로 조금씩 변형하며 사용하면 될 것 같다.

#include <iostream>
#include <queue>
#include <utility>
using namespace std;

int main(void){
    ios:: sync_with_stdio(0);
    cin.tie(0);

    int arr[100][100] = 
    { {1,1,1,0,1,0,0,0,0,0},
    {1,0,0,0,1,0,0,0,0,0},
    {1,1,1,0,1,0,0,0,0,0},
    {1,1,0,0,1,0,0,0,0,0},
    {0,1,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0} };

    bool isVisited[100][100];

    pair<int, int> dir[4] = {
        pair<int, int>(-1, 0),
        pair<int, int>(1, 0),
        pair<int, int>(0, -1),
        pair<int, int>(0, 1)
    };

    int n = 7, m = 10;

    queue<pair<int, int> > q;

    isVisited[0][0] = 1;
    q.push(pair<int, int>(0, 0));

    while(!q.empty()){
        pair<int, int> cur = q.front();
        q.pop();

        cout << "(" << cur.first << "," << cur.second << ") -> ";

        for(int i = 0; i < 4; i++){
            int adjX = cur.first + dir[i].first;
            int adjY = cur.second + dir[i].second;

            if(adjX < 0 || adjX >= n || adjY < 0 || adjY >= m) continue;
            if (isVisited[adjX][adjY] == true || arr[adjX][adjY] == 0) continue;

            isVisited[adjX][adjY] = true;
            q.push(pair<int, int>(adjX, adjY));
        }
    }
    cout << "end" << "\n";
}

선언과 초기화

---

• line 10 ~ 17 : 다차원 배열을 선언한다. (주어진 다차원 배열을 저장한다.)
• line 19 : 각 칸의 방문 여부를 확인하기 위해 다차원 배열과 같은 크기의 배열을 선언한다.
• line 21 ~ 26 : 22줄부터 순서대로 배열의 상, 하, 좌, 우 좌표를 구할 방향 좌표이다.
• line 28 : 각 칸의 좌표를 담을 pair 형 queue를 선언한다.

탐색 과정

---

• line 32 : 시작점인 (0,0)을 방문했다고 명시한다. 시작점은 들어오는 다차원 배열에 따라 다르다.

• line 33 : queue에 시작점인 (0,0)을 삽입한다.

• line 35 : queue에 남은 노드가 없을 때까지 반복한다.
• line 36 ~ 37 : queue의 가장 앞에 있는 노드를 확인한다.
• line 39 : 탐색 과정을 출력한다.
• line 41 : 해당 칸의 상하좌우로 인접한 칸을 탐색한다.
• line 45 : 탐색하는 칸이 범위 밖일 경우 탐색하지 않는다.
• line 46 : 인접한 칸이 이미 방문했던 칸이거나 빈 칸이라면 탐색하지 않는다.
• line 47 ~ 48 : 방문한 칸을 명시하고 queue에 방문한 칸을 삽입한다.

💡 주의해야 할 점

1. 시작점에 방문했다는 표시를 해야 한다.
2. 방문한 칸을 큐에서 뺄 때가 아닌 큐에 넣을 때 명시해야 한다. (같은 칸이 큐에 여러 번 들어가게 되어 시간 초과나 메모리 초과의 위험성 있음)
3. 인접한 칸의 범위를 벗어날 경우 탐색할 수 없다.