[BOJ/C++] 미로 탐색(2178번)

1. 개요

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

2178번: 미로 탐색

1-1. 설명

N x M 크기 배열로 표현되는 미로가 있다. 미로가 이동할 수 있는 칸은 1, 이동할 수 없는 칸은 0으로 나타낸다. 이때 미로가 주어졌을때 (1, 1)에서 출발해 (N, M)의 위치로 이동할때 지나야 하는 최소 칸의 수를 구하는 프로그램을 작성한다. 

1-2. 제한 사항

 - 첫 줄에 두 정수  N, M이 주어지며, 각각 2이상 100 이하

 - 다음 N개 줄에 M개의 미로 정수가 주어짐

---

2. 구현

2-1. 풀이

최단 거리를 검색해야 하므로, BFS로 구현하면 된다. DFS로 구현할 때에는 현 이동 개수를 갱신하여 도달했을 때의 값중 최소값을 저장하면 된다. 굳이 조건을 더 넣으면서 DFS로 구현할 이유가 없으므로, BFS로 구현하였다. 

2-2. 코드

#include <iostream>
#include <algorithm>
using namespace std;

struct Node {
    int x;
    int y;
    int count;
};

int N, M, result = 0;
Node queue[10000];
int map[101][101];
bool visited[101][101];

int dirX[4] = {1, -1, 0, 0};
int dirY[4] = {0, 0, 1, -1};

void BFS(int x, int y);

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // 이동가능 1, 불가능 0
    // (1, 1) -> (N, M)
    // 최소 칸수

    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        string nums;
        cin >> nums;
        int idx = 1;
        for (char num : nums) map[i][idx++] = num - '0';
    }

    BFS(1, 1);

    cout << result;

    return 0;
}

void BFS(int x, int y) {
    int front = -1;
    int rear = -1;
    visited[x][y] = true;
    queue[++rear] = { x, y, 1 };

    while (front != rear) {
        Node cur = queue[++front];

        if (cur.x == N && cur.y == M) result = cur.count;

        for (int i = 0; i < 4; i++) {
            int nextX = cur.x + dirX[i];
            int nextY = cur.y + dirY[i];

            if (nextX > 0 && nextX <= N && nextY > 0 && nextY <= M && map[nextX][nextY] == 1) {
                if (visited[nextX][nextY]) continue;
                visited[nextX][nextY] = true;
                queue[++rear] = { nextX, nextY, cur.count + 1 };
            }
        }
    }
}