[문제해결 알고리즘] BFS :: 연습문제 :: 미로탈출 로봇 대회(정올) :: C언어

0. 문제 설명

정올에서 미로탈출 로봇 대회를 개최하였다.

대회에 사용되는 미로는 가로(X), 세로(Y) 100이하의 크기이며, 미로를 한 칸 이동하는 데는 1초가 걸린다.

 

 

 

 

대회에 참가중인 민성이는 자신의 로봇이 가장 빨리 미로를 탈출하기 위해 미로의 모양을 입력받아서 도착점까지 가장 빠른 길을 찾으려고 한다.

프로그램을 작성하여 민성이를 도와주자.

 

입력 형식

첫줄에 미로의 크기 X, Y(1≤X, Y≤100)가 주어진다. 둘째 줄에 출발점 x, y 좌표와 도착점 x, y 좌표가 공백으로 구분하여 주어진다. 셋째 줄부터 미로의 정보가 길은 0, 벽은 1로 공백이 없이 들어온다.

 

출력 형식

첫줄에 출발점에서 도착점까지 가장 빠른 시간을 출력한다.

 

입력 예시

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

 

출력 예시

9

 

 

1. 문제 풀이

#include <stdio.h>
#define MAXXY (100)
int X, Y; // 가로(X), 세로(Y)
char map[MAXXY+10][MAXXY+10];
int sx, sy, ex, ey; // 출발점 xy좌표 sx, sy, 도착점 xy좌표 ex, ey


// 1. 입력 처리 함수
void InputData(void) {
	scanf("%d %d", &X, &Y);
	scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
	for (int r = 1; r <= Y; r++) {
		// 숫자들이 공백없이 들어오므로 문자열로 받는 것이 편함
		scanf("%s", &map[r][1]);
	}
}

// 2. BFS 탐색을 위한 fifo 자료구조 Queue 구현
#define MAXQ (MAXXY*MAXXY+10)
typedef struct {
	int x, y, t; // 위치 정보 x, y와 해당 좌표의 가중치(즉 시작점으로부터의 거리)를 저장
} QUE;
QUE que[MAXQ];
int rp, wp; // read pointer와 write pointer
void push(int x, int y, int t) {
	// 해당 노드를 큐에 넣는다 = 다음 차례가 오면 탐색할 거라는 뜻
	// 따라서 노드를 큐에 넣기 전에 넣어도 되는 지 체크
	// 1. 범위 체크 & 길인지 체크
	if (map[y][x] != '0') { // 길이면 '0', 벽이면 '1', 방문했던 길이면 '2', 맵에서 범위를 벗어나면 0
		return;
	}
	map[y][x] = '2';//방문표시
	que[wp].x = x;
	que[wp].y = y;
	que[wp].t = t;
	wp++;
}

QUE pop(void) {
	return que[rp++];
}

QUE top(void) {
	return que[rp];
}

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

int Solve(void) {
	// 1. 초기화
	wp = rp = 0; // 큐 초기화
	int dy[] = { -1,1,0,0 };
	int dx[] = {0,0,-1,1}; // 현재노드의 다음 노드는 상하좌우 노드 순으로 탐색할 거임
	// 2. 시작 지점 큐에 넣기
	push(sx, sy, 0);
	// 3. 반복문 
	while (!empty()) {
		QUE cur = pop();
		if (cur.x == ex && cur.y == ey) return cur.t;
		for (int i = 0; i < 4; i++) {
			push(cur.x + dx[i], cur.y + dy[i], cur.t + 1);
		}
	}
}
int main(void) {
	InputData();
	int ans = Solve();
	printf("%d\n", ans);
}

 

 

 

문제 출처 : http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=934&sca=99 

JUNGOL