BOJ 2178 미로 탐색 c++

백준 2178번 미로 탐색 문제

 

먼저 X, Y는 pair<int, int>를 위해 define 한다.

board는 string배열이기 때문에 실제로는 char 형태 2차원 배열이다.

(string이 char * 의 역할을 하므로.)

dx[n] + dy[n] 는 항상 상, 하, 좌, 우 중 하나를 나타낸다.

 

Q에 하나씩 넣으면서 dist[0][0]으로부터 목표지점까지 걸리는 시간을 잰다.

nx, ny는 현재 위치의 상, 하, 좌, 우를 반영한 값이다.

 

이 때 범위가 밖으로 벗어나는 경우 continue 해주고,

dist[nx][ny]가 이미 방문한 적이 있는 경우, 즉 `>=0` 인 경우 혹은 board[nx][ny]가 '1'이 아닌 경우

continue 시켜준다.

 

Q가 빌때까지 이를 반복해주면 

dist[row-1][col-1] 에는 dist[0][0]부터 해당 지점까지 걸린 시간이 담긴다.

이것을 출력하면 끝.

#include <bits/stdc++.h>
using namespace std;
# define X first
# define Y second

int row;
int col;
string board[102];
int dist[102][102];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> row >> col;
    for (int i = 0 ; i < row; i++) 
        cin >> board[i];
    for (int i = 0; i < row; i++)
        fill(dist[i], dist[i] + col, -1);
    queue<pair<int, int>> Q;
    dist[0][0] += 1;
    Q.push({0, 0});
    while (!Q.empty()) {
        auto cur = Q.front();
        Q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 0 || ny < 0 || nx >= row || ny >= col)
                continue;
            if (dist[nx][ny] >= 0 || board[nx][ny] != '1')
                continue;
            dist[nx][ny] = dist[cur.X][cur.Y] + 1;
            Q.push({nx, ny});
        }
    }
    cout << dist[row-1][col-1] + 1;
}