미로의 최단거리 통로(BFS) / c++ / 제한시간 없음

▣ 문제

7*7 격자판 미로를 탈출하는 최단경로의 경로수를 출력하는 프로그램을 작성하세요. 경로수는 출발점에서 도착점까지 가는데 이동한 횟수를 의미한다. 출발점은 격자의 (1, 1) 좌표이고, 탈 출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 도로이다. 격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면

위와 같은 경로가 최단 경로이며 경로수는 12이다.

 

▣ 입력설명

- 첫 번째 줄부터 7*7 격자의 정보가 주어집니다.

 

▣ 출력설명

- 첫 번째 줄에 최단으로 움직인 칸의 수를 출력한다. 도착할 수 없으면 -1를 출력한다.

 

<코드>

#pragma warning(disable:4996)
#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;

int map[7][7];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };

struct cur {
	int x;
	int y;
	cur(int a, int b) {
		x = a;
		y = b;
	}
};

int main() {
	int i, j, cnt = 1, ans = 0;
	queue<cur> Q;
	for (i = 1; i <= 7; i++)
		for (j = 1; j <= 7; j++)
			scanf("%d", &map[i][j]);

	Q.push(cur(1, 1));
	map[1][1] = 1;
	while (!Q.empty()) {
		int xx, yy;
		cur pos = Q.front();
		Q.pop();
		for (i = 0; i < 4; i++) { 
			xx = pos.x + dx[i];
			yy = pos.y + dy[i];
			if (xx < 1 || xx>7 || yy < 1 || yy>7) continue;
			if (map[xx][yy] == 0) {
				Q.push(cur(xx, yy));
				map[xx][yy] = map[pos.x][pos.y] + 1;
				if (xx == 7 && yy == 7) {
					ans = map[xx][yy];
					break;
				}
			}
		}
	}
	if (map[7][7] == 0) printf("-1\n");
	else printf("%d\n", ans - 1);
	return 0;
}

코드의 키포인트는 map[ ][ ]의 값에 BFS 탐색할떄 레벨값으로 바꿔서 저장시키는것이다.

 

한번 움직일때마다 이전 경로(Path)의 값보다 1씩 증가시키면 미로를 탐색하면서 BFS의 레벨값을 알 수 있다.

 

.

 

예전에 해보았던 유형이었음

 

미로 최단거리는 BFS로