<알고리즘 문제풀이&연습>/[C++] 백준

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

사용자 BlockDMask 2017. 10. 16. 09:00
반응형
  • 안녕하세요. 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. 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
//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<intint> > q;   //queue for bfs search
    q.push(pair<intint>(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<intint>(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;
}
 
cs


4. 인증


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

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

반응형