[BFS] 백준 2178번 미로 탐색

www.acmicpc.net/problem/2178

2178번: 미로 탐색

수행기간 : 2021/1/13~1/13

미로탐색에서 처음으로 queue<pair> 이라는 것을 사용하여봤다. pair는 이차원 배열의 인덱스를 표현할 때 사용하고, 특히 미로탐색같이 최단경로를 구하는 BFS를 구현할 때 이용한다. 블로그를 쓰기전 BFS 문제를 몇개 풀어본 적이 있었는데  최근에는 큐를 써서 구현하려고 노력중이다. 다만 아직도 배열이 익숙한지 혼용하는 부분이 보이긴 한다. 그리고 BFS의 특징(?), 문제를 몇개 풀다보니 확실히 미로나 길찾기 등 좌표를 활용 할 수 있다면, x와y 좌표를 처음부터 설정한 후 코딩을 하면 생각하기가 수월해진다.

//개관: 최단거리를 구하는 문제이므로 BFS를 통해 풀것이다.
#include<iostream>
#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;
int map[101][101];
int visit[101][101];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int n, m;

void bfs(int a, int b) {
	queue <pair <int,int>> q;
	visit[a][b] = 1;
	q.push(make_pair(a, b));
	while (!q.empty()) {
		int nowA = q.front().first;
		int nowB = q.front().second;
		q.pop();
		for (int i = 0; i < 4;i++) {
			int nextX = nowA + dx[i];
			int nextY = nowB + dy[i];
			if ((nextX >= 0 && nextX <= n) && (nextY >= 0 && nextY <= m)) {
				if (map[nextX][nextY] == 1 && visit[nextX][nextY] == 0) {
					q.push(make_pair(nextX, nextY));
					visit[nextX][nextY] = visit[nowA][nowB] + 1;
				}
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			scanf("%1d", &map[i][j]);
		}
	}
	bfs(0, 0);

	if ( n >= 2 && n <= 100 && m >= 2 && m <= 100)
		printf("%d\n", visit[n-1][m-1]);
	return 0;
}