백준 2178: 미로 탐색

문제 요약

2차원 배열의 미로가 주어지면, (1,1)에서 (n,m)의 위치로 이동할 최소의 칸 수를 출력한다. 이 때, 1은 이동할 수 있는 칸을, 0은 이동할 수 없는 칸을 의미한다.
배열의 입력은 붙어서 입력으로 주어진다.

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS

문제 풀이

2차원 배열을 탐색하고자 하므로 queue역시 queue<pair<int,int>>의 형태로 나와야 할 것이다. 첫 번째는 탐색하는 정점의 행번호로, 두 번째는 정점의 열 번호로 생각하였다.

2차원 배열의 탐색 방법으로 dir[][]을 정의하여 for문으로 간단하게 탐색하였다.
탐색하며 큐에 넣을 때, ary[ny][nx] == '1'를 확인하여, 탐색가능한 곳인지 확인하여야 한다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;

string ary[100];
bool visited[101][101];
int dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };

int main()
{
	int n, m, level = 0, qsize;
	bool sol = false;

	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> ary[i];
	queue<pair<int, int>> q;
	q.push({0,0});
	visited[0][0] = true;
	while (!q.empty()) {
		level++;
		qsize = q.size();
		while (qsize--) {
			auto y = q.front().first;
			auto x = q.front().second;
			q.pop();
			if (y == n - 1 && x == m - 1) {
				sol = true;
				break;
			}
			for (int i = 0; i < 4; i++) {
				int nx = x + dir[i][0], ny = y + dir[i][1];
				if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
					if (!visited[ny][nx] && ary[ny][nx] == '1') {
						visited[ny][nx] = true;
						q.push({ny,nx});
					}
				}
			}
		}
		if (sol) break;
	}
	printf("%d", level);
	return 0;
}