C++로 확인하는 행렬 내 두 셀 사이의 경로 존재 여부

이 글에서는 주어진 행렬(matrix) 안에서 두 셀 사이에 경로가 존재하는지 확인하는 C++ 프로그램을 살펴보겠습니다.

문제 정의

0, 1, 2, 3의 값을 가질 수 있는 4×4 정사각형 행렬이 주어졌다고 가정해 봅시다. 각 숫자의 의미는 다음과 같습니다.

0: 빈 벽 (이동 불가)
1: 출발점(Source)
2: 도착점(Destination)
3: 빈 셀 (자유롭게 이동 가능)

행렬에는 출발점과 도착점이 각각 하나씩만 존재합니다. 프로그램은 상하좌우 네 방향으로만 이동할 수 있다고 가정하고(대각선 이동은 허용되지 않음), 출발점에서 도착점까지 갈 수 있는 경로가 있는지 판별합니다.

접근 방법

이 문제는 그래프 탐색 알고리즘인 BFS(너비 우선 탐색)를 이용해 해결할 수 있습니다. 먼저 행렬의 각 셀을 그래프의 정점(vertex)으로 변환하고, 이동 가능한 인접 셀들 사이에 간선(edge)을 연결합니다. 이렇게 만든 그래프 위에서 출발점부터 도착점까지 BFS를 수행하면 경로의 존재 여부를 알 수 있습니다.

예제 코드

#include<bits/stdc++.h>
using namespace std;
// 주어진 배열로부터 가능한 그래프를 생성하는 클래스
class use_graph {
    int W;
    list <int> *adj;
    public :
    use_graph( int W ){
        this->W = W;
        adj = new list<int>[W];
    }
    void add_side( int source , int dest );
    bool search ( int source , int dest);
};
// 간선을 추가하는 함수
void use_graph :: add_side ( int source , int dest ){
    adj[source].push_back(dest);
    adj[dest].push_back(source);
}
// BFS(너비 우선 탐색)를 수행하는 함수
bool use_graph :: search(int source, int dest) {
    if (source == dest)
        return true;
    // 방문 여부 배열 초기화
    bool *visited = new bool[W];
    for (int i = 0; i < W; i++)
        visited[i] = false;
        list<int> queue;
        // 출발점을 방문 처리하고 큐에 삽입
        visited[source] = true;
        queue.push_back(source);
        // 인접한 정점들을 차례로 탐색
        list<int>::iterator i;
        while (!queue.empty()){
            source = queue.front();
            queue.pop_front();
            for(i=adj[source].begin();i!=adj[source].end(); ++i) {
                if (*i == dest)
                    return true;
                if (!visited[*i]) {
                    visited[*i] = true;
                    queue.push_back(*i);
                }
            }
        }
        // 도착점에 도달하지 못한 경우
    return false;
}
// 해당 좌표가 이동 가능한 셀인지 검사하는 함수
bool is_okay(int i, int j, int M[][4]) {
    if ((i < 0 || i >= 4) || (j < 0 || j >= 4 ) || M[i][j] == 0)
        return false;
    return true;
}
// 행렬을 그래프로 변환하고 경로 탐색을 수행하는 함수
bool find(int M[][4]) {
    int source , dest ;
    int W = 4*4+2;
    use_graph g(W);
    int k = 1 ;
    for (int i =0 ; i < 4 ; i++){
        for (int j = 0 ; j < 4; j++){
            if (M[i][j] != 0){
                if ( is_okay ( i , j+1 , M ) )
                    g.add_side ( k , k+1 );
                if ( is_okay ( i , j-1 , M ) )
                    g.add_side ( k , k-1 );
                if (j < 4-1 && is_okay ( i+1 , j , M ) )
                    g.add_side ( k , k+4 );
                if ( i > 0 && is_okay ( i-1 , j , M ) )
                    g.add_side ( k , k-4 );
            }
        if( M[i][j] == 1 )
            source = k ;
        if (M[i][j] == 2)
            dest = k;
            k++;
        }
    }
    return g.search (source, dest) ;
}
int main(){
    int M[4][4] = { { 0 , 3 , 0 , 1 }, { 3 , 0 , 3 , 3 }, { 2 , 3 , 0 , 3 },{ 0 , 0 , 3 , 0 }};
    (find(M) == true) ?
    cout << "Possible" : cout << "Not Possible" <<endl ;
    return 0;
}

실행 결과

Not Possible

코드 설명

위 코드의 동작 과정을 단계별로 정리하면 다음과 같습니다.

그래프 생성: use_graph 클래스가 인접 리스트 방식으로 그래프를 구성합니다. 행렬의 각 셀은 1번부터 순서대로 번호가 매겨집니다.
간선 연결: find() 함수는 행렬을 순회하면서 값이 0이 아닌 셀을 기준으로, 상하좌우에 있는 이동 가능한 셀과 간선을 연결합니다. 벽(0)이거나 행렬 범위를 벗어나는 경우에는 연결하지 않습니다.
출발점·도착점 기록: 행렬을 순회하는 동안 값이 1인 셀은 출발점으로, 값이 2인 셀은 도착점으로 저장됩니다.
BFS 탐색: search() 함수가 출발점에서 시작해 큐(queue)를 이용해 너비 우선 탐색을 진행하며, 도착점에 도달하면 true, 큐가 비어도 도달하지 못하면 false를 반환합니다.

예제 행렬에서는 출발점(1)과 도찷점(2) 사이가 벽(0)으로 막혀 있어 이동이 불가능하므로, 최종 결과로 "Not Possible"이 출력됩니다.