[c++]백준 2178 미로찾기

www.acmicpc.net/problem/2178

2178번: 미로 탐색

문제

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

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

예제 입력 1 
4 6
101111
101010
101011
111011
예제 출력 1 
15

예제 입력 2 
4 6
110110
110110
111111
111101
예제 출력 2 
9

예제 입력 3 
2 25
1011101110111011101110111
1110111011101110111011101
예제 출력 3 
38

예제 입력 4 
7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111
예제 출력 4 
13

풀이과정 

1.데이타 입력 받기

2.해결 방법

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

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

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

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

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

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

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

를 확인하면 됩니다.

 

1.입력 방법 

행렬을 입력 받아야 하므로 처음하시는 분들은 입력 방법 부터 혼란이 있을 수 있는 것 같습니다.

입력 방법은 2가지가 있으며 입력에 따라서 이후 처리 방법도 같이 수정이 되어야 합니다.

 

1)int로 입력 

int N, M ;// 세로(행) ,가로(열)  
int map[MAXN][MAXN]; 

void InputData(){
    scanf("%d %d", &N, &M);
    for( int i=0; i < N; i++){
        for( int j=0; j < M; j++){
            scanf("%1d", &map[i][j] );
        }
    }
}

 

2)string으로 입력 받기

char map[][];으로 정의를하고 &map[i][1]로 입력을 받으면 \null까지 입력을 받게 된다.

int N, M ;// 세로(행) ,가로(열)  
char map[MAXN][MAXN];

void InputData(){
    cin >> N >> M;
    for( int i=1; i <= N; i++){
        cin >> &map[i][1];
    }
}

 

 

  1 /*baekjoon 2178 미로탐색 BFS*/                                                                                                                                                     
  2 #include <bits/stdc++.h>
  3 using namespace std;
  4 
  5 #define MAXN ((int) 1e2 + 10)
  6 int N, M ;// 세로(행) ,가로(열)  
  7 char mmap[MAXN][MAXN];
  8 int mapCheck[MAXN][MAXN];
  9 int dy[4]= {-1,1,0,0};
 10 int dx[4]= {0,0,1,-1};
 11 
 12 bool isInside(int a, int b){
 13     return (a>=1 && a<=N) && (b>=1 && b<=M);
 14 }
 15 int BFS(){
 16     int x=1,y=1,nx,ny;
 17     queue<pair<int,int>> q;
 18     q.push(pair<int, int>(y, x));
 19     mapCheck[y][x] = 1;
 20 
 21     while(!q.empty()) {
 22         y = q.front().first;
 23         x = q.front().second;
 24         q.pop();
 25         if(y==N && x==M) {return mapCheck[y][x];}
 26         for (int i = 0; i < 4; i++) {
 27             ny = y + dy[i];
 28             nx = x + dx[i];
 29 
 30             if(isInside(ny , nx ) && mapCheck[ny][nx] == 0 &&  mmap[ny][nx] == '1'){
 31                 mapCheck[ny][nx] = mapCheck[y][x] + 1;
 32                 q.push( pair<int, int>(ny, nx) );
 33             }
 34         }
 35     }
 36     return 1;
 37 
 38 }
 39 void InputData(){
 40     cin >> N >> M;
 41     for( int i=1; i <= N; i++){
 42         cin >> &mmap[i][1];
 43     }
 44 }
 45 int main(){
 46     ios_base::sync_with_stdio(0);
 47     cin.tie(0);
 48 
 49     InputData();
 50     cout << BFS() << endl;
 51     return 0;
 52 }
 53 /*baekjoon 2178 미로탐색 BFS*/