2178번 (silver 1)

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

BFS로 푸는 가장 보편적인 문제인 미로에서 최소거리 탐색문제이다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void BFS(vector<vector<int>>&);
int main() {
	cin.tie(0)->sync_with_stdio(false);
	int N, M;
	cin >> N >> M;
	vector<vector<int>> arr(N + 2, vector<int>(M + 2, 0));

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

	BFS(arr);

	cout << arr[N][M];

	return 0;
}

void BFS(vector<vector<int>>& arr) {
	queue<pair<int, int>> q({ make_pair(1,1) });
	vector<vector<bool>> visit(arr.size(), vector<bool>(arr[0].size(), false));
	int n = arr.size() - 2, m = arr[0].size() - 2;
	while (!q.empty()) {
		int i = q.front().first, j = q.front().second;
		q.pop();
		if (n == i && m == j) {
			break;
		}
		if (visit[i + 1][j] == false && arr[i + 1][j] != 0) {
			q.push(make_pair(i + 1, j));
			arr[i + 1][j] = arr[i][j] + 1;
			visit[i + 1][j] = true;
		}
		if (visit[i][j + 1] == false && arr[i][j + 1] != 0) {
			q.push(make_pair(i, j + 1));
			arr[i][j + 1] = arr[i][j] + 1;
			visit[i][j + 1] = true;
		}
		if (visit[i - 1][j] == false && arr[i - 1][j] != 0) {
			q.push(make_pair(i - 1, j));
			arr[i - 1][j] = arr[i][j] + 1;
			visit[i - 1][j] = true;
		}
		if (visit[i][j - 1] == false && arr[i][j - 1] != 0) {
			q.push(make_pair(i, j - 1));
			arr[i][j - 1] = arr[i][j] + 1;
			visit[i][j - 1] = true;
		}

	}
}