Boj 2178 c++ 눈물의 미로탐색

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

 

문제는 위와 같다. 우선 문제를 그래프 탐색으로 풀기 위해서는 반드시 너비 우선 탐색을 해야 한다. 필자와 같이 태그를 확인 안하고 DFS로 구현했다가 시간을 날리는 불상사를 겪지 않도록 주의해야 한다. BFS로 찾아야만 하는 이유는 DFS로 경로를 구하면 가장 먼저 나오는 경로만을 참조하여 출력하기 때문에 문제에서 요구하는 최단경로가 아니게 된다. 

BFS와 DFS의 특징, 사용처는 이후 문제풀이에도 중요하기 때문에 챗지피티와의 대화를 인용하겠다.

---

🔍 DFS vs BFS 개념 정리

항목DFS (Depth-First Search)BFS (Breadth-First Search)

구조	스택(재귀 포함)	큐 (Queue)
탐색 방식	깊이 우선: 한 방향으로 계속 진행	너비 우선: 인접한 노드들을 레벨 순으로 탐색
경로	처음 찾는 경로가 최단 경로라는 보장 없음	처음 도착한 경로가 최단 경로
최단 거리 구할 수 있나?	일반적으로 ❌ (추가 작업 필요)	✅ 자동으로 가능
사용 예	모든 경로 탐색, 백트래킹, 퍼즐, 조합 탐색	최단 거리, 레벨 탐색, 미로, 네트워크 확산 등
속도/공간	재귀 깊이에 민감 / 적은 공간	큐에 모든 노드를 담아야 하므로 공간 사용 많음

 

여기서 가장 중요한 점은 BFS는 레벨순으로 탐색하기 때문에 각각의 경로에 대해서 길이가 개별적으로 저장되고, 이러한 특성으로 인해 가장 처음으로 목적지에 도달하는 경로가 최단경로인 것이다.

 

문제를 풀이하기에 앞서 코드를 구상해보아야 한다. 우선 첫번째 경로가 벽인 경우는 예외처리를 해준다. 또한 끝까지 출구를 찾지 못한 경우에도 -1을 출력하도록 처리해줘야 한다. 그 이후에는 최단경로를 찾아야 하는 방법을 생각해보아야한다. 우선 레벨별로 경로를 탐색하는 BFS의 특성상 각 경로별로 출발지점에서 부터 해당 경로까지의 길이를 동적으로 누적해서 저장해나가는 방식을 생각해보았다. 어짜피 출력되는 값은 최단경로까지의 칸 수 뿐이기 때문이다. 이렇게 하면 처음에 입력받은 미로공간에 대해서 방문처리도 자연스럽게 가능하게 된다. 

미로는 격자 그래프의 형태로 존재한다. 격자그래프 풀이의 기본 요소는 4방향 탐색이다. 

dx, dy라는 배열을 만들어 {1, -1, 0, 0}   {0, 0, -1, -1} 의 값을 각각 저장해둔다. 이렇게 함으로써 반복문을 사용하여 해당 배열의 원소들을 각각 기존의 미로지점 인덱스에 더해준다면 격자그래프상에서 상, 하, 좌, 우로 움직일 수 있게 된다.

여기서부터는 일반 BFS문제오 비슷하다. 방문하지 않고, 탐색이 가능한지점(벽이 없는 곳)에 대해서 탐색을 하기 위해 큐에 push하여 이후의 탐색을 약속한다. 그리고 4방향 탐색이 모두 끝난 이후에는 q의 첫번째 값을 pop해준다. 이렇게 while문 안에서 레별별 탐색을 이어나간다. 이때, 탐색을 하기 위해 queue에 값을 push하는 시점에 출발지점 부터 해당 지점까지의 거리를 누적하는 코드를 작성한다. 또한 경로에 도달했을 경우에는 함수를 종료한다.

#include<iostream>
#include<vector>
#include<string>
#include<queue>

using namespace std;

int N, M;

vector<vector<int>> v(101, vector<int>(101));
vector<vector<int>> walk(101, vector<int>(101));
queue<pair<int, int>> q;
bool found=false;
void maze(int U, int V){



   int dx[4]={-1, 1, 0, 0};
   int dy[4]={0, 0, 1, -1};

   q.push({U, V});
   walk[U][V]=1;

   while(!q.empty()){

        U=q.front().first;//U, V값 초기화
        V=q.front().second;

       for(int i=0; i<4; i++){


            int nx=dx[i]+U;//4방향 탐색
            int ny=dy[i]+V;

            if(nx<1 || ny<1 || nx>N || ny>M)//인덱스 이탈 방지
            continue;


            if(v[nx][ny] && walk[nx][ny]==0){//탐색가능, 미방문인 경우
                q.push({nx, ny});//탐색 예약
                walk[nx][ny]=walk[U][V]+1;//경로 길이 누적
                if(nx==N && ny==M){//목표지점에 도달한 경우
                    found=true;
                    return;
                }

               }
            }
          q.pop();//4방향 탐색이 끝난 이후 pop
    }

}


int main(){

    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>N>>M;

    for(int i=1; i<=N; i++){
            string str;//미로 입력 받기
            cin>>str;
            for(int j=1; j<=M; j++){
                v[i][j]=str[j-1]-'0';
            }


        }

    maze(1, 1);
    if(!found || v[1][1]==0)
        cout<<"-1";
    else
        cout<<walk[N][M];


}