미로 탈출 로봇(BFS)

문제 설명

---

미로탈출 로봇 대회를 개최하였다. 대회에 사용되는 미로는 가로(W), 세로(H) 100이하의 크기이며, 미로를 한 칸 이동하는 데는 1초가 걸린다.

로봇이 출발점에서 도착점까지 가장 빨리 이동할 경우 걸리는 시간을 구하는 프로그램을 작성하시오.

입력 설명

---

첫 줄에 미로의 크기 W, H(1≤W, H≤100)가 주어진다.
둘째 줄에 출발점 w, h 좌표와 도착점 w, h 좌표가 공백으로 구분하여 주어진다.
셋째 줄부터 미로의 정보가 길은 0, 벽은 1로 공백이 없이 들어온다.
주의 사항으로, 좌표는 좌측상단이 가장 작은 위치이며 이 위치의 좌표는 (1,1)이다.
출력 설명
첫 줄에 출발점에서 도착점까지 가장 빠른 시간을 출력한다.

입력 예시

---

8 7
1 2 7 5
11111111
00000111
10110011
10111001
10111101
10000001
11111111

출력 예시

---

9

부가정보

---

[입력 예시 2]
8 10
1 1 7 9
00000101
11001000
10000010
01101010
00000110
01010000
01110110
10000100
10011101
01000001

[출력 예시 2]
16

---

[입력 예시 3]
5 5
1 1 5 5
00000
01101
00100
01110
00000

[출력 예시 3]
8

#include <stdio.h>
#include <string.h>
#define MAXN (100)
int W, H;//가로, 세로 크기
int sw, sh, ew, eh;//출발 가로세로, 도착 가로세로 좌표
char map[MAXN+10][MAXN+10];//지도정보
 
int visited[MAXN+10][MAXN+10];
struct QUE{
    int h, w, t;
};
 
struct QUE que[MAXN * MAXN + 10];
int wp, rp;
 
void push(int h, int w, int t){
    if (map[h][w] != '0') return;
    if (visited[h][w]) return;
    visited[h][w]=1;
    que[wp].h=h; que[wp].w=w; que[wp].t=t; wp++;
}
void pop(void){
    rp++;
}
struct QUE front(void){
    return que[rp];
}
int empty(void){
    return wp==rp;
}
 
int BFS(void){
    int dh[] = {-1, 1, 0, 0};
    int dw[] = {0, 0, -1, 1};
    //0.초기화
    memset(visited, 0, sizeof(visited));
    wp = rp = 0;
    //1.시작위치 큐에 저장
    push(sh, sw, 0);
    //2.반복문
    while (!empty()){
        struct QUE cur = front(); pop();
        if ((cur.h==eh) && (cur.w==ew)) return cur.t;//성공
        for (int i=0; i<4; i++){
            push(cur.h+dh[i], cur.w+dw[i], cur.t+1);
        }
    }
    //3.실패(이 문제는 이런 경우 없음)
    return -1;//디버깅을 위해...
}
 
void InputData(void){
    scanf("%d %d", &W, &H);
    scanf("%d %d %d %d", &sw, &sh, &ew, &eh);
    for (int i=1; i<=H; i++){
        scanf("%s", &map[i][1]);
    }
}
 
int main(void){
    int ans = -1;
    InputData();//입력
 
    ans = BFS();//여기서부터 작성
 
    printf("%d\n", ans);//출력
    return 0;
}