[백준/C++] 2178번 : 미로 탐색

문제

 

설명

미로를 탈출하는 최단 거리를 구하는 문제이다.

최단 거리를 구해야 하기에 깊이 우선 탐색이 아닌 너비 우선 탐색을 사용하였고,

입력이 붙어서 들어오기에 먼저 string으로 받고 인덱스 하나 하나 집어 넣어주었다.

bfs를 도는 중에는 상하좌우를 검사하여 인덱스를 벗어나지 않고/방문하지 않았고/이동할 수 있는 위치일 때 큐에 삽입하였다.

 

그리고 처음 알았는데 queue.push 대신 queue.emplace를 쓰면 속도도 더 빠르고 pair같은 구조체를 make_pair를 사용하지 않고 바로 집어 넣을 수 있어 편했다.

 

최단 거리를 구하는게 조금 어려웠는데, 그냥 2차원 배열을 새로 만들어서 기록해주는게 제일 편한듯 했다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int N, M;
bool visited[101][101];
int maze[101][101];
int dist[101][101];

// 동서남북
int x[4] = { 1, -1, 0, 0 };
int y[4] = { 0, 0, 1, -1 };

int bfs(int a, int b) {
	visited[a][b] = true;

	queue<pair<int, int>> q;
	q.emplace(a, b);

	while (!q.empty()) {
		pair<int, int> top = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = top.first + x[i];
			int ny = top.second + y[i];
			if (!visited[nx][ny] and nx >= 0 and ny >= 0 and nx <= N and ny <= M and maze[nx][ny] == 1) {
				q.emplace(nx, ny);
				visited[nx][ny] = true;
				dist[nx][ny] = dist[top.first][top.second] + 1;
			}
		}
	}

	return dist[N][M];
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		string a;
		cin >> a;
		for (int j = 1; j <= M; j++) {
			maze[i][j] = a[j - 1] - '0';
		}
	}

	int answer = bfs(1, 1);

	cout << answer + 1;

	return 0;
}