[Algorithm] BFS 격자 탐색 (dx, dy + dz)

BFS는 그래프 탐색에 자주 사용되는 알고리즘입니다.

기본적인 BFS는 인접 행렬, 인접 리스트 등 노드와 노드 사이의 연결 관계를 나타낸 그래프를 Queue를 이용하여 탐색합니다.

 

이번 글에서는 주어진 데이터가 인접 행렬, 인접 리스트가 아닌 경우의 예시를 살펴보도록 하겠습니다.

 

 

---

 

1. 입력 데이터 및 조건

 

주어지는 데이터의 예시는 다음과 같습니다.

// pseudo code
int arr[][] = {
    0, 1, 1, 0, 1,
    1, 0, 1, 1 ,1,
    1, 0, 0, 1, 0,
    1, 1, 1, 1, 0,
    0, 1, 1, 1, 0
};

위와 유사한 2차원 배열이 주어집니다.

주어진 배열의 노드 (X, Y)에 연결된 노드는 다음과 같습니다.

• (X+1, Y)
• (X-1, Y)
• (X, Y+1)
• (X, Y-1)

 

즉. 한 점에 대하여 상, 하, 좌, 우 방향으로의 탐색이 가능합니다.

 

2. 인접 행렬, 인접 리스트 만들기 ?

 

위 데이터를 인접 행렬, 혹은 리스트로 만드는 경우, 노드가 25개가 됩니다.

구체적으로, N*M의 배열이 주어질 경우, 인접 행렬의 경우 (N*M)^2의 크기를 가지게 됩니다.

 

메모리 차원에서 매우 비효율적이기 때문에, 다른 방법을 찾아보는 것이 좋겠습니다.

 

3. dx, dy 

 

이번 글의 핵심 내용이 되겠습니다.

위와 같은 조건에 대한 탐색을 수행할 경우, 해당 데이터를 인접행렬, 리스트로 변환하는 것은 비 효율적입니다.

대신, 저 배열이 가지고 있는 특징에 대해 생각해볼 경우, 다음과 같은 아이디어를 도출할 수 있습니다.

노드 (X, Y)에 인접한 노드는 (X, Y)에 대하여 다음의 값을 더한 노드입니다.
- (-1, 0)
- (1, 0)
- (0, -1)
- (0, 1)

해당 값은 다음과 같이 정의되어 사용할 수 있습니다.

// pseudo code
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };

for(int i=0; i<4; i++) {
    x = x + dx[i];
    y = y + dy[i];
}

 

4. BFS

 

문단3의 아이디어를 BFS에 적용해보도록 하겠습니다.

우선, 인접 리스트를 이용한 BFS 코드의 일부입니다.

void bfs(...) {
    queue.push(start);
    visited[start] = true;
    
    while(!queue.empty()) {
        int current = queue.pop();
        
        for(auto& i : graph[current]) {
            if(!visited[i]) {
                queue.push(i);
                visited[i] = true;
            }
        }
    }
}

이제 dx, dy를 사용한 BFS코드를 살펴보도록 하겠습니다.

void bfs(...) {
    queue.push({x, y});
    visited[x][y] = true;
    
    while(!queue.empty()) {
        pair<int, int> cur = queue.pop();
        int cur_x = cur.x;
        int cur_y = cur.y;
        int visitData = arr[cur_x][cur_y];
        
        for(int i=0; i<4; i++) {
            // Caution
            if(!visited[cur_x + dx[i]][cur_y + dy[i]]) {
                queue.push({cur_x + dx[i], cur_y + dy[i]});
                visited[cur_x + dx[i]][cur_y + dy[i]] = true;
            }
        }
    }
}

주요 변경점은 다음과 같습니다.

• Queue에 들어가는 값이 노드의 가중치가 아니라, 노드의 인덱스입니다.
• 2차원 배열에 대한 탐색이므로, visited또한 2차원 배열이 되었습니다.
• 다음 노드를 탐색하는 과정이, 현재 노드의 인덱스에 dx, dy배열을 순회한 값이 됩니다.

 

위 코드를 실제로 사용하려면, 다음 노드를 탐색하는 과정 (Caution 주석이 있는 코드)에 한 가지 예외 처리가 추가되어야 합니다.

탐색 과정에서 배열에 직접적인 접근을 하기 때문에, Invalid Index Exceptino을 주의해야 합니다.

 

5. 방향 및 확장

 

본문의 dx, dy를 다시 살펴보도록 하겠습니다.

// pseudo code
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };

위 코드를 인덱스 순서대로 살펴볼 경우, 탐색하는 배열의 위치는 상, 하, 좌, 우가 됩니다.

다음의 값에 따라 인덱스를 변경할 경우, 탐색 방향을 변경할 수 있습니다.

// Up
dx = -1; dy = 0;

// Down
dx = 1; dy = 0;

// Left
dx = 0; dy = -1;

// Right
dx = 0; dy = 1;

 

또한, 위 아이디어는 3차원에도 적용이 가능합니다.

이 경우, 4방향이 6방향이 됩니다.

// pseudo code
int dx[] = { -1, 1, 0, 0, 0, 0 };
int dy[] = { 0, 0, -1, 1, 0, 0 };
int dz[] = { 0, 0, 0, 0, -1, 1 };

순회 방법은 2차원과 동일합니다.

 

---

 

BFS의 다른 아이디어에 대해 알아보았습니다.

이 글이 로직 구성에, 문제 풀이에, 새로운 아이디어의 창출에 도움이 되셨기를 바랍니다.

 

감사합니다.