[C++] 백준 2178 미로 탐색

백준 '미로 탐색' 문제 보러가기

저번에 풀었던 '토마토' 문제와 비슷하다.
지나간 블록의 차례를 이전 블록의 위치를 기준으로 하나씩 증가해가며 표시해주면 쉽게 풀 수 있는 문제이다.

#include <iostream>
#include <queue>
#include <string>
using namespace std;
int N,M, cnt =0;
int xDir[4]={0,0,-1,1}, yDir[4]={1,-1,0,0};
queue<pair<int, int>>q;

int main() {
    cin>> N>>M;

    int maze[N][M];
    for(int i=0;i<N;i++){
        string str;
        cin>>str;
        for(int j=0;j<str.length();j++){
            maze[i][j]=str[j]-48;
        }
        
    }
    
    q.push(make_pair(0,0));
    while(!q.empty()){
        pair<int, int> p = q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int xPos = p.first + xDir[i], yPos = p.second + yDir[i];
            if(xPos < 0 || xPos >= M || yPos < 0 || yPos >= N) continue;
            if(maze[yPos][xPos] == 1){
                if(yPos == N-1 && xPos == M-1 && maze[yPos][xPos] !=1){
                    if(maze[p.second][p.first]+1 < maze[yPos][xPos]) maze[yPos][xPos] = maze[p.second][p.first]+1;
                }
                else{
                    maze[yPos][xPos] = maze[p.second][p.first]+1;
                    q.push(make_pair(xPos,yPos));
                }
            }
        }   
    }
    cout << maze[N-1][M-1];

}

하나 신경써 준 부분은, 최종 목적지인 (N,M)지점에 도달할 수 있는 경로가 여러가지일 수 있다는 점이다. 가장 작은 수를 출력하기 위해서 최종 목적지에 도착했을 때는 이전보다 더 작은 수일 때만 갱신이 되도록 조건문을 달아주었다.

*썸네일은 여기서 만들었다. 재미있는 토이 프로젝트라 사용 & 공유해본다.