백준 2178 - 미로 탐색

문제링크

BFS하면서 visit array에 boolean값 대신 predecessor처럼 쓰자.

정확히 말하면 predecessor라기보다는 그 노드까지 오기에 걸렸던 최단거리를 저장하면 최단거리를 추적할 수 있다.

#include <stdio.h>

#define N 100
int map[N+1][N+1];
int visited[N+1][N+1];

typedef struct point {
    int x;
    int y;
} Point;

Point q[N*N];
int qhead, qtail;

int main() {
    int i,j;
    int n,m;
    int order;
    char c;
    scanf("%d%d", &n, &m);
    while ((getchar()) != '\n');
    for (i=1; i<=n; i++) {
        for (j=1; j<=m; j++) {
            map[i][j] = getchar() - '0';
        }
        while ((c = getchar()) != '\n' && c != EOF);
    }

    visited[1][1] = 1;
    q[qtail++] = (Point){1, 1};

    while (q[qhead].x != 0 && q[qhead].y != 0) {
        Point u = q[qhead++];

        int x,y;

        y = u.y-1; x = u.x;
        if (y >= 1 && map[y][x] && visited[y][x] == 0) {
            visited[y][x] = visited[u.y][u.x]+1;
            q[qtail++] = (Point){x, y};
        }
        y = u.y+1; x = u.x;
        if (y <= n && map[y][x] && visited[y][x] == 0) {
            visited[y][x] = visited[u.y][u.x]+1;
            q[qtail++] = (Point){x, y};
        }
        y = u.y; x = u.x-1;
        if (x >= 1 && map[y][x] && visited[y][x] == 0) {
            visited[y][x] = visited[u.y][u.x]+1;
            q[qtail++] = (Point){x, y};
        }
        y = u.y; x = u.x+1;
        if (x <= m && map[y][x] && visited[y][x] == 0) {
            visited[y][x] = visited[u.y][u.x]+1;
            q[qtail++] = (Point){x, y};
        }
    }

    printf("%d\n", visited[n][m]);

    return 0;
}