백준 2178:미로 탐색

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

백준 2178번 미로 탐색입니다.

최단 거리를 계산할때, 배열에 인덱스에 접근할때마다 전에 있는 인덱스의 cnt를 하나 증가시킨 값을 넣어요. 결국 최종 종착점에는 이동한 거리가 찍히겠죠?

밑에는 제코드예요.

#include <iostream>
#include <queue>
#define MAX 105
 
using namespace std;
 
typedef struct rc {
    int r;
    int c;
}Position;
 
int cnt;
int N, M;
bool visited[MAX][MAX];
int maze[MAX][MAX];
 
bool isSafe(int r,int c) {  //범위 벗어나는지 체크
    if ((r<0 || r>N) || (c<0 || c>M)) return false;
    else return true;
}
 
void bfs() {
    Position pos; pos.r = 0; pos.c = 0;
    visited[0][0] = true;
    queue<Position> q;
    q.push(pos);
    while (!q.empty()) {
        int r = q.front().r, c = q.front().c;
        if (r == N - 1 && c == M - 1) break;
                                                                         //현재 위치에서 갈 수 있는 점을 찾아요
        if (maze[r - 1][c] && !visited[r - 1][c] && isSafe(r - 1, c)) {  //길이 있고, 방문하지 않았고, 범위 벗어나지 않으면
            pos.r = r - 1; pos.c = c;                                    //그 점의 좌표를 큐에 넣어요
            visited[r - 1][c] = true;
            maze[r - 1][c] = maze[r][c] + 1;
            q.push(pos);
        }
        if (maze[r + 1][c] && !visited[r + 1][c] && isSafe(r + 1, c)) {
            pos.r = r + 1; pos.c = c;
            visited[r + 1][c] = true;
            maze[r + 1][c] = maze[r][c] + 1;
            q.push(pos);
        }
        if (maze[r][c - 1] && !visited[r][c - 1] && isSafe(r, c - 1)) {
            pos.r = r; pos.c = c - 1;
            visited[r][c - 1] = true;
            maze[r][c - 1] = maze[r][c] + 1;
            q.push(pos);
        }
        if (maze[r][c + 1] && !visited[r][c + 1] && isSafe(r, c + 1)) {
            pos.r = r; pos.c = c + 1;
            visited[r][c + 1] = true;
            maze[r][c + 1] = maze[r][c] + 1;
            q.push(pos);
        }
 
        q.pop();
    }
}
 
int main(void) {
    std::ios::sync_with_stdio(false);
    
    cin >> N >> M;
    int many = 0;
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < M; k++) {
            char way; cin >> way;
            maze[i][k] = way - '0';
        }
    }
 
    bfs();
    cout << maze[N - 1][M - 1] << '\n';
 
    return 0;
}