[BOJ] #2178 미로 탐색

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

2178번: 미로 탐색

---

가중치가 없는 그래프에서의 최단경로 찾기. 역시나 BFS를 활용하는 문제이다. 인접리스트 형식이 아닌 숫자 행렬로 입력이 주어지기 때문에 상하좌우 연산을 통해서 그래프를 탐색하고, 목적지까지의 거리를 계산하기 위해 중간중간에 거치는 정점마다의 거리값 배열인 dist를 이용하여 해결했다.

다만 도중에 scanf에서 &arr[i][j]와 같이 이중반복문으로 배열의 인덱스에 직접 접근하여 입력했는데, 숫자가 공백없이 주어지다 보니 입력 과정에서 문제가 생기는 것 같았다. 같은 BFS 매커니즘의 코드에서 int형식이 아닌 char 형식으로 입력받도록 고쳤다.

또한 stdio입출력과 iostream입력을 서로 섞어서 쓰다보니 한번 더 틀렸었는데, 모두 stdio 입출력으로 고쳐주니까 그제서야 맞힐 수  맞힐 수 있었다. 정작 문제 접근 방식은 잘 잡고 들어갔는데 이상한 곳에서 두번이나 틀려버렸다고 할 수 있겠다.

#include <stdio.h>
#include <queue>

#define MAX 101

using namespace std;

int N,M;
char arr[MAX][MAX];
bool visited[MAX][MAX] = { false };
int dist[MAX][MAX];

int Dx[4] = { -1, 1, 0, 0 };
int Dy[4] = { 0, 0, -1, 1 };
            //상  하  좌  우 

void BFS(int x, int y) {
    queue<pair<int,int>> Q;
    Q.push(make_pair(x,y));
    visited[x][y] = true;

    dist[x][y] = 1;

    while(!Q.empty()) {
        int X = Q.front().first;
        int Y = Q.front().second;
        Q.pop();

        for (int i=0; i<4; i++) {
            int newX = X + Dx[i];
            int newY = Y + Dy[i];

            if ((newX >= 0 && newX < N) && (newY >= 0 && newY < M)) {
                if (visited[newX][newY] == false && arr[newX][newY] == '1') {
                    Q.push(make_pair(newX, newY));
                    visited[newX][newY] = true;

                    dist[newX][newY] = dist[X][Y] + 1;
                }
            }
        }
    }
}

int main() {
    scanf("%d %d", &N, &M);

    for (int i=0; i<N; i++) scanf("%s", arr[i]);

    BFS(0,0);
    printf("%d\n", dist[N-1][M-1]);

    return 0;
}

int로 입력받아서 한번, stdio와 iostream 입출력을 섞어 써서 한번씩 틀렸다...