[c++] 백준 2178, 미로 탐색

백준 2178

🌲 문제 요약

NxM 크기의 배열로 표현되는 미로가 주어질 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때까지 지나야 하는 칸 수의 최소를 구하는 문제.

🌲 문제 풀이

같은 가중치를 가진 그래프에서 최단거리를 구하는 문제이므로, BFS을 이용하여 해결한다.
상하좌우 방향으로 arr를 탐색하여, 만일 arr[ny][nx]의 값이 존재하고 visited[ny][nx]의 값이 0이라면 visited[ny][nx] = visited[y][x] + 1, q.push({ny, nx})의 연산을 수행한다.
while문을 통해 q의 내용이 없을 때까지 반복한다.

🌲 주의

입력값이 간격 없이 주어지므로, scanf("%1d", &arr[i][j])를 통해 한 글자씩 입력받도록 한다.

🌲 코드

#include <bits/stdc++.h>

using namespace std;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
int n, m, y, x;
int arr[105][105], visited[105][105];

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &arr[i][j]);
		}
	}
	visited[0][0] = 1;
	queue<pair<int, int>> q;
	q.push({0, 0});
	while (q.size()) {
		tie(y, x) = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
			if (arr[ny][nx] && !visited[ny][nx]) {
				visited[ny][nx] = visited[y][x] + 1;
				q.push({ny, nx});
			}
		}
	}
	cout << visited[n - 1][m - 1] << '\n';
	
	return 0;
}