[백준 / C언어] 미로탐색 (2178)

 

 

📌 문제 링크

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

2178번: 미로 탐색

 

 

BFS를 통해 문제를 해결했다.

큐를 만들어서 좌표와 이동한 횟수를 관리했으며,

큐가 빌 때까지 4방향을 탐색하고, 길이 아니거나 이미 방문한 길이라면 continue를 해주고

원하는 좌표에 도착하면 return해준다.

처음과 끝을 포함하지 못했기 때문에 +2를 해주었다.

 

👩‍💻 전체코드

#include <stdio.h>
int N, M;
int graph[100+10][100+10];
int visited[100+10][100+10];

typedef struct _ {
    int x; int y; int count;
} QUE;

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
QUE queue[100*100+10];

int rp, wp;

void push(int x, int y, int count) {
    queue[wp].x =x;
    queue[wp].y = y;
    queue[wp++].count = count;
    visited[x][y] = 1;
}

void pop(void) {
    rp++;
}

QUE front(void) {
    return queue[rp];
}

int empty(void) {
    return rp == wp;
}


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

int solve(void) {
    int nx, ny;
    rp = 0;
    wp = 0;
    QUE cur;
    push(0,0,0);
    while(!empty()) {
        cur = front(); pop();
        for(int i = 0; i < 4; i++) {
            nx = cur.x +dx[i];
            ny = cur.y + dy[i];
            if(nx < 0 || ny < 0 || nx > N + 1 || ny > M + 1) {
                continue;
            } 
            if(graph[nx][ny] != 1) {
                continue;
            }
            if(visited[nx][ny] == 1) continue;
            if((nx == (N-1)) && (ny == (M-1))) {
                return cur.count;
            }
            push(nx, ny, cur.count + 1);
        }
    }
}

int main() {
    inputData();
    int ans = solve();
    printf("%d\n", ans+2);
    return 0;
}