C++ / 백준 / 1261 / 알고스팟

문제

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

1261번: 알고스팟

문제풀이

입력을 받는 matrix벡터와 벽을 몇 번 부쉈는지 나타내는 visit벡터를 선언한다.

BFS로 문제를 풀었으며 queue에는 { y, x, 벽 부순 횟수 } 순으로 입력을 push 했다.

네 방향을 탐색하면서 다음 칸의 visit벡터를 보면서 값이 -1 (방문을 하지 않음)이거나

벽이 있고 cnt+1보다 크면 큐에 push 하고, 벽이 없고 cnt보다 크면 방문한다.

모든 탐색이 끝나 큐가 비었으면 BFS함수를 종료하고 visit[N][M]을 출력하면 된다.

N과 M은 1 이상이므로 1, 1 일수도 있다. 이 경우 문제에 나왔듯이 항상 뚫려있으므로 0을 출력하면 된다.

 

 

코드

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

int N, M;
vector<vector<int>>matrix;
vector<vector<int>>visit;
vector<int> dx = { -1, 1, 0, 0 };
vector<int> dy = { 0, 0, 1, -1 };

void BFS() {
	queue<vector<int>>q;
	q.push({ 1,1,0 });
	while (!q.empty()) {
		int y = q.front()[0];
		int x = q.front()[1];
		int cnt = q.front()[2];
		q.pop();
		for (int idx = 0; idx < 4; ++idx) {
			int n_y = y + dy[idx];
			int n_x = x + dx[idx];
			if (n_y >= 1 && n_y <= N && n_x >= 1 && n_x <= M) {
				if (matrix[n_y][n_x] == 0) {
					if (visit[n_y][n_x] > cnt || visit[n_y][n_x] == -1) {
						visit[n_y][n_x] = cnt;
						q.push({ n_y,n_x,cnt });
					}
				}
				else {
					if (visit[n_y][n_x] > cnt + 1 || visit[n_y][n_x] == -1) {
						visit[n_y][n_x] = cnt + 1;
						q.push({ n_y, n_x, cnt + 1 });
					}
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	string number = "";
	int y = 0, x = 0;
	cin >> M >> N;

	matrix = vector<vector<int>>(N + 1, vector<int>(M + 1, 0));
	visit = vector<vector<int>>(N + 1, vector<int>(M + 1, -1));

	for (y = 1; y <= N; ++y) {
		cin >> number;
		for (x = 1; x <= M; ++x)
			matrix[y][x] = number[x - 1] - '0';
	}

	BFS();

	if (visit[N][M] == -1) visit[N][M] = 0;
	cout << visit[N][M];
}