[2178] 미로 탐색

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

가장 쉬운 bfs문제입니다.

최소의 칸 수를 구하라? 즉 bfs를 이용해서 가장 먼저 도달하는 너비를 출력하라는 말입니다.

bfs는 항상 최적을 보장하기 때문입니다.

#include <stdio.h>
 
const int QUEUE_SIZE = 100 * 100 * 4;
 
typedef struct qs {
    int x, y, b;
}qs;
 
 
typedef struct queue {
    qs data[QUEUE_SIZE];
    int front, rear;
 
    queue() {
        front = rear = 0;
    }
 
    int empty() {
        return front == rear;
    }
 
    void push(qs d) {
        rear = (rear + 1) % QUEUE_SIZE;
        data[rear] = d;
    }
 
    qs pop() {
        front = (front + 1) % QUEUE_SIZE;
        return data[front];
    }
}queue;
 
 
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, -1, 0, 1 };
char map[100][100];
int visit[100][100];
 
int main() {
    int m, n;
    scanf("%d %d", &m, &n);
 
    getchar();
 
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            map[i][j] = getchar();
        }
        getchar();
    }
 
    queue q;
    q.push(qs{0, 0, 1});
    visit[0][0] = 1;
    
    while (!q.empty()) {
        qs front = q.pop();
 
        if (front.x == m - 1 && front.y == n - 1) {
            printf("%d", front.b);
            break;
        }
 
        for (int i = 0; i < 4; i++) {
            int nx = front.x + dx[i];
            int ny = front.y + dy[i];
 
            if (nx < 0 || ny < 0 || nx >= m || ny >= n || visit[nx][ny]) continue;
            if (map[nx][ny] == '0') continue;
 
            visit[nx][ny] = 1;
            q.push(qs{ nx, ny, front.b + 1 });
        }
 
    }
 
    return 0;
}