[백준 2178] 미로탐색 (BFS-너비우선탐색)

• 안녕하세요. BlockDMask 입니다.

• 오늘은 BFS algorithm 기반으로 미로탐색 문제를 풀어보았습니다.

0. 제목

• 백준 2178 미로탐색(BFS-너비우선탐색)

• BOJ 2178 MAZE(BFS-너비우선탐색)

1. 문제 설명

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

4x6 예시.

[101111]

[101010]

[101011]

[111011]

미로에서 1은 이동할 수 있는 칸을 나타내고

0은 이동할 수 없는 칸을 나타냅니다.

이러한 미로가 주어졌을 때

[0,0] 에서 출발하여 배열기준 [N-1, M-1] 의 위치로 이동할 때

 지나야 하는 최소의 칸 수를 구하는 프로그램을 구현하면 됩니다.

입력 : 첫째 줄에 두 정수 N, M (2<= N, M <= 100)이 주어지고, 다음 N개의 줄에는 M개의 정수로 미로가 주어집니다.

출력 : 첫째 줄에 지나야하는 최소의 칸 수(시작과 끝 포함)를 출력합니다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어집니다.

2. 풀이 과정

-> 탐색을 하면서 지나간 길을 등록하는 2차원 배열이 필요합니다.

-> 지나간 길을 알릴 뿐만 아니라 몇번째에 왔는지 숫자를 기록하면서 이동해야 합니다.

-> queue를 이용하여 BFS 알고리즘으로 구현합니다.

-> 2차원 배열이므로 up, down, left, right를 갈때 

1) 해당 점이 map 내부에 있는지

2) 해당 점이 지나온길이 아닌지

3) 해당 점이 1 인지 (가는 길인지)

를 확인하면 됩니다.

+ queue 자료구조에 pair 클래스를 이용하여 좌표 y, 좌표 x를 받았습니다.

3. 코드

//https://www.acmicpc.net/problem/2178
//BOJ_2178_미로탐색
 
#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
 
int n;  //row
int m;  //column
 
bool map[100][100];  //true - can go, false - can't go
int check[100][100]; //지나온길 기록
int dir[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}}; //up, down, left, right check.
 
//input
void In(){
    cin >> n >> m;
 
    for(int i=0; i<n; i++){
        for(int j=0; j<m ;j++) {
            int b;
            scanf("%1d", &b);
 
            if(b==1){
                map[i][j] = true;
            }
        }
    }
}
 
//output
void Out(int num){
    printf("%d\n", num);
}
 
//check [y, x] is in or not
bool isInside(int a, int b){
    return (a >= 0 && a < n) && (b >=0 && b < m);
}
 
 
int bfs(){
    int cur_y=0, cur_x=0;   //current y, x
 
    queue<pair<int, int> > q;   //queue for bfs search
    q.push(pair<int, int>(cur_y,cur_x));
    check[cur_y][cur_x] = 1;    //bfs가 지나가면서 몇번째만에 그 점에 접근했는지
 
    while(!q.empty()){
 
        cur_y = q.front().first;
        cur_x = q.front().second;
        q.pop();
 
        if((cur_y == n-1) && (cur_x == m-1)) break; //도착지점 
        (위의 탈출조건은 없어도 무방합니다)
 
        for(int i=0; i<4; i++){
            //up, down, left, right !!
            int next_y = cur_y + dir[i][0];
            int next_x = cur_x + dir[i][1];
 
            //next y, x가 배열 내부에 있고, check 2차원배열에 기록된적 없고, map에 true로 되어있으면
            if(isInside(next_y, next_x) && check[next_y][next_x]==0 && map[next_y][next_x]){
                check[next_y][next_x] = check[cur_y][cur_x] +1; //이전 방문값 + 1 = 다음 방문
                q.push(pair<int, int>(next_y, next_x)); //방문한 곳 push push
            }
        }
    }
 
    /*  bfs로 만든 check 배열 출력해보기
    for(int i=0;i<n; i++){
        for(int j=0; j<m ; j++){
            cout << check[i][j];
        }
        cout << endl;
    }
    */
 
    return check[n-1][m-1];
}
 
 
int main(void){
    In();
    Out(bfs());
    return 0;
}
 

4. 인증

문제출처 - https://www.acmicpc.net/problem/2178

감사합니다. 도움이 되었다면 하트 꾹꾹!!