2017_11_29<백준> 2178번 미로 탐색

출처:https://www.acmicpc.net/problem/2178

문제

 

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

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

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

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

문제 해결 과정:

-BFS 사용

-각 칸마다 위 아래 옆 옆 총 네곳을 검사, 밑에 경우를 제외하고 큐에 넣는다

-0보다 작거나 그래프 밖으로 나가면 무시

-방문한적 있으면 무시

-방문한 곳이 0이면 무시

-N-1,M-1칸에 도착하면 멈추고 실행한 횟수(result) 출력

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
 
int surroundR[4] = { -1,1, 0,0};
int surroundC[4] = { 0,0,-1,1 };
 
struct Node {
    int x;
    int y;
};
 
int main() {
    int N, M;
    cin >> N >> M;
    int Miro[100][100] = { 0 };
    bool visited[100][100] = { false };
 
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; j++) {
            scanf_s("%1d", &Miro[i][j]);
        }
    }
    
    queue<Node> Q;
    visited[0][0] = true;
    Node start;
    start.x = 0;
    start.y = 0;
    Q.push(start);
    int result = 1;
 
    while (!Q.empty()) {
        int Q_size = Q.size();
        for (int i = 0; i < Q_size; i++) {
            int r = Q.front().x;
            int c = Q.front().y;
            Q.pop();
            if (r == N - 1 && c == M - 1) {
                cout << result << endl;
                return 0;
            }
 
 
            for (int d = 0; d < 4; d++) {
                int nr = r + surroundR[d];
                int nc = c + surroundC[d];
            
                if (nr < 0 || nr >= N || nc < 0 || nc >= M) {
                    continue;
                }
 
                if (!Miro[nr][nc]) {
                    continue;
                }
 
                if (visited[nr][nc]) {
                    continue;
                }
 
                visited[nr][nc] = true;
                Node temp;
                temp.x = nr;
                temp.y = nc;
                Q.push(temp);
            }
        }
 
        result++;
 
    }
    return 0;
}