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

문제: www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

 

문제풀이

 

BFS를 이용해 (1, 1) 부터 (N, M) 까지의 최단거리를 구하는 문제이다.

 

미로가 공백없이 한 행씩 입력되므로 맵을 문자열로 선언했다.

 

 

코드

#include <iostream>
#include <queue>

using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int N, M;
    cin>>N>>M;

    string board[100]; //한 행씩 입력되므로 문자열로 선언
    int dx[4] = {-1,1,0,0};
    int dy[4] = {0,0,-1,1};
    int dist[100][100]; //거리 기록을 위한 배열

    for(int i=0; i<N; i++)  fill(dist[i], dist[i]+M, 0); //거리를 모두 0으로 초기화


    for(int i=0; i<N; i++){ //input
        cin>>board[i];
    }

    queue<pair<int, int>> q;
    q.push({0,0}); //시작점
    dist[0][0] = 0;

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

        for(int dir=0; dir<4; dir++){
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];

            if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            if(dist[nx][ny] || board[nx][ny] == '0') continue;

            dist[nx][ny] = dist[cur.first][cur.second] + 1;
            q.push({nx,ny});
        }
    }
    
    cout<<dist[N-1][M-1]+1;

    return 0;
}

 

 

결과