백준2178번:미로 탐색

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

2178번: 미로 탐색

이 문제는 좌표(n,m)까지 최단 경로를 구하는 것이다. 최단 경로를 구하는 문제는 DFS보다 BFS가 훨씬 효율적이다.

방문하면 그값을 전에 값에 1씩더하면서 가면 n,m을 도달하게 되고 그 값이 즉 값이다. 그리고 다른 경로로 온다고 해도 이미 최단으로 방문되었으므로 값이 바뀔 일은 없다.

1		1	1	1
1		1		1	1
1		1		1
1		1		1
1	1	1		1	1

1		11	12	13
2		10		14	15
3		9		15
4		8		16
5	6	7		17	18

이렇게 방문하기 전에 값을 1씩 더하면 맨 끝에 도달한 값이 나오고 그게 최단경로이다.

#include<iostream>
#include <queue>
#include <cstdio>
using namespace std;
#pragma warning(disable : 4996)
int px[4] = { 1,-1,0,0 };
int py[4] = { 0,0,1,-1 };
int d[100][100];                 //1과 0 값 넣기
bool check[100][100];             //방문 체크
int sum[100][100];              //몇번쨰 방문인지 적는 배열
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int k = 0; k < m; k++) {
			scanf("%1d", &d[i][k]);
		}
	}
	queue<pair<int, int>> q;
	q.push(make_pair(0, 0));
	check[0][0] = true;
	sum[0][0] = 1;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + px[i];
			int ny = y + py[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m) {        //칸의 위 아래 오른쪾 왼쪾이 지정된 범위 안일 경우
				if (check[nx][ny] == false && d[nx][ny] == 1) {  //방문안했고 값이 1인 경우 
					q.push(make_pair(nx, ny));
					sum[nx][ny] = sum[x][y] + 1;           //그 전칸에 1을 더해준다
					check[nx][ny] = true;              //방문처리
				}
			}
		}
	}
	printf("%d", sum[n - 1][m - 1]);        //최단경로 값
	return 0;
}