JArchive 프로그래밍 일기

문제

미로 탐색 백준 2178번

리뷰

오늘의 교훈. 문제를 정독하자..!!!

미로의 시작은 (0, 0) 끝은 (N-1, M-1) 로 정해져있다.

최단 경로를 구하는 거니까 BFS로 탐색했다.

토마토 문제와 비슷하게, 현재칸에 숫자를 저장할 때 큐에서 꺼낸 숫자 + 1을 해줬다.

        for(int i = 0; i < 4; i++){ // 상하좌우 살핀다 

            int xx = x + dx[i];
            int yy = y + dy[i];

            if(A[xx][yy] == 1 && boundary(xx, yy)){ // 범위 내에 있고, 이동가능한 1이라면. 
                q.push(make_pair(xx, yy));
                A[xx][yy] = A[x][y] + 1;  // 큐에서 꺼낸 칸 숫자 + 1
            }
        }

상하좌우가 N, M 행렬 인덱스 범위 안에 있는지는 boundary 함수를 이용해서 true/false 확인해줬다.

int N, M;  // 행, 열  

// 상하좌우 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1}; 


bool boundary(int i, int j){
    return (i >= 0 && i < N && j >=0 && j < M) ? 1:0;
}

코드

#include <iostream> 
#include <queue>
#define MAX 101
using namespace std;

int N, M;  // 행, 열  
int A[MAX][MAX];

// 상하좌우 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1}; 


bool boundary(int i, int j){
    return (i >= 0 && i < N && j >=0 && j < M) ? 1:0;
}

void BFS(){

    queue<pair<int,int> > q;

    q.push(make_pair(0, 0));

    while(!q.empty()){

        pair<int,int> now = q.front();
        q.pop();

        int x = now.first; // 큐에서 꺼낸 칸의 좌표 (행x 열y)
        int y = now.second;

        for(int i = 0; i < 4; i++){ // 상하좌우 살핀다 

            int xx = x + dx[i];
            int yy = y + dy[i];

            if(A[xx][yy] == 1 && boundary(xx, yy)){ // 범위 내에 있고, 이동가능한 1이라면. 
                q.push(make_pair(xx, yy));
                A[xx][yy] = A[x][y] + 1;  // 큐에서 꺼낸 칸 숫자 + 1
            }
        }
    }

    cout << A[N-1][M-1];
}  

int main(void){

    cin >> N >> M ; // 행, 열  

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

         char ch[MAX];
         scanf("%s", &ch);

         for(int j = 0; j < M; j++){
             A[i][j] = ch[j]-48;  
        } 
    }  

    BFS();

    return 0;    
}