4. 1661 : 미로 탈출 로봇

문제 원본 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=934&sca=50&sfl=wr_hit&stx=1661&sop=and

JUNGOL | 미로 탈출 로봇 > 문제은행

문제 풀이 : 

#include<stdio.h>
#define MAX (101)
int map[MAX][MAX]; //지도
int visit[MAX][MAX]; // 방문체크
// 큐 구조체 설계
typedef struct _node {
	int r, c, time;
}NODE;
NODE que[MAX * MAX]; //큐배열 생성 -> Full 상태 없게 하기 위해 충분히 크게!
int rp, wp;
int R, C, sr, sc, er, ec;
void In_Que(int r, int c, int time) {
	que[wp].r = r;
	que[wp].c = c;
	que[wp].time = time;
	wp++;
}
void Out_Que(NODE* p) {
	*p = que[rp++];
}
int BFS(void) {
	int dr[4] = { -1,1,0,0 }, dc[4] = { 0,0,-1,1 }; //상하좌우
	int i, nr, nc;
	NODE q;
	In_Que(sr, sc, 0);
	visit[sr][sc] = 1; // 방문체크
	while (rp < wp) { // 큐 empty check
		//q = que[rp++];
		Out_Que(&q); // 현재 좌표
		if (q.r == er && q.c == ec) return q.time;
		for (i = 0; i < 4; i++) {
			nr = q.r + dr[i];
			nc = q.c + dc[i];
			if (nr<1 || nr>R || nc<1 || nc>C) continue; // 범위 벗어나면 스킵
			if (visit[nr][nc] == 1) continue;
			if (map[nr][nc] == 0) { //연결점 찾기(길)
				In_Que(nr, nc, q.time + 1);
				visit[nr][nc] = 1;
			}
		}
	}
	return -1; //큐가 빈상태(예외체크 - 미로탈출의 경우 예외경우 없음)
}
void input(void) {
	int i, j;
	scanf("%d %d", &C, &R);
	scanf("%d %d %d %d", &sc, &sr, &ec, &er);
	for (i = 1; i <= R; i++) {
		for (j = 1; j <= C; j++) {
			scanf("%1d", &map[i][j]);
		}
	}
}
int main(void) {
	int sol;
	input();
	sol = BFS();
	printf("%d\n", sol);
	return 0;
}