2178 - 미로찾기 (C언어)

문제 자체가 파악이 어려운 것은 아니다. 단순하게 1이 있는 경로로만 움직일 수 있고 0은 벽이며, 1이 있는 경로로만 움직였을 때 최소 경로를 구해내면 되는 수기 때문이다. 입력으로 길을 찾을 수 없는 경우에 대한 처리도 존재하지 않으니, 문제에서 주어진 대로 따라가는 것이 핵심이다.

입력을 받고나서 길을 찾는 순서를 어떻게 결정한 것인지가 굉장히 문제이다. 배열의 크기를 단순하게 이동하며, 지나온 경로에 대해 따로 처리를 하고 다시 지나가지 않게끔 하여 진행하는 방법도 있겠지만, 사실 이 사고 방식을 가지고 큐를 통해 선입선출형식으로 길찾기를 진행한다면 굉장히 쉽게 해결이 가능하다.

큐에는 (0,0)의 데이터를 넘겨준다
nx[i] 와 ny[i]를 반복문을 통해 값을 수정하며
주변에 이동 가능한 길이 있고 maze[new_x][new_y]
한 번도 이동한적이 없는 경우 !visited[new_x][new_y]
방문 표시를 하고 visited[new_x][new_y] = visited[x][y] + 1;
rear를 증가시키며, 큐에 새로운 좌표를 넣어준다.
그리고 큐는 선입선출 형식이기 때문에, 들어온 순서대로 계속 좌표를 서치하며 나갈 것이다.

#include <stdio.h>
#include <stdlib.h> 

#define MAX_N 101
#define MAX_M 101

int maze[MAX_N][MAX_M] = {};
int nx[4] = {-1, 1, 0, 0};
int ny[4] = {0, 0, -1, 1};
int visited[MAX_N][MAX_M] = {}; 

typedef struct Queue {
    int qx; // visited x
    int qy; // visited y
} Queue;

void find_load(int x, int y) {
    Queue q[MAX_N * MAX_M];
    int front = -1;
    int rear = -1;
    rear++;
    q[rear].qx = x;
    q[rear].qy = y;
    visited[x][y] = 1;

    while (front < rear) {
        front++;
        x = q[front].qx; // x realloc
        y = q[front].qy; // y realloc

        for (int i = 0; i < 4; i++) {
            int new_x = x + nx[i];
            int new_y = y + ny[i];

            if (new_x >= 0 && new_x < MAX_N && new_y >= 0 && new_y < MAX_M) {
                if (!visited[new_x][new_y] && maze[new_x][new_y]) {
                    visited[new_x][new_y] = visited[x][y] + 1;
                    rear++;
                    q[rear].qx = new_x;
                    q[rear].qy = new_y;
                }
            }
        }
    }
}

int main(void) {
    int N, M;

    scanf("%d %d", &N, &M);

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%1d", &maze[i][j]);
        }
    }

    find_load(0, 0);

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

    return 0;
}