[C++] 백준 14442번 벽 부수고 이동하기 2

BFS를 사용해서 문제를 풀었습니다.

visit배열에 벽을 부순 횟수를 저장하며 탐색하며,
벽을 부순 횟수가 더 적게 방문하면 그 값으로 변환됩니다.
그리고 더 크면 접근하지 못하므로,
재방문도 막으며, 더 최적일 때만 접근이 가능하게 됩니다.

 

#include <iostream>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 987654321
using namespace std;

bool flag = false;
int n, m, k;
int countNum = MAX;
int map[1010][1010];
int visit[1010][1010];
int moveX[4] = { 0, 1, 0, -1 };
int moveY[4] = { 1, 0, -1, 0 };
queue<vector<int> >q;

void BFS()
{
	int a, b, c, d;
	int x, y;
	vector<int> v;
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	v.push_back(0);
	q.push(v);
	while (!q.empty()) {
		a = q.front()[0];
		b = q.front()[1];
		c = q.front()[2];
		d = q.front()[3];
		q.pop();

		for (int i = 0; i < 4; ++i) {
			x = moveX[i] + a;
			y = moveY[i] + b;

			if (x == n && y == m) {
				while (!q.empty()) {
					q.pop();
				}
				++c;
				countNum = min(countNum, c);
				return;
			}
			if (abs(map[x][y]) != 1 && d < visit[x][y] && d < k + 1) {
				visit[x][y] = d;
				vector<int> element;
				element.push_back(x);
				element.push_back(y);
				element.push_back(c + 1);
				element.push_back(d);
				q.push(element);
			}
			if (map[x][y] == 1 && d < visit[x][y] && d < k) {
				vector<int> element;
				element.push_back(x);
				element.push_back(y);
				element.push_back(c + 1);
				element.push_back(d + 1);
				visit[x][y] = d + 1;
				q.push(element);
			}
		}
	}
	return;
}

int main(int argc, char* argv[])
{
	string s;

	cin >> n >> m >> k;

	memset(map, -1, sizeof(map));
	memset(visit, 30, sizeof(map));

	if (n == 1 && m == 1) {
		cout << "1" << endl;
		return 0;
	}

	for (int i = 1; i <= n; ++i) {
		cin >> s;
		for (int j = 1; j <= m; ++j) {
			map[i][j] = s[j - 1] - '0';
		}
	}

	BFS();

	if (countNum == MAX) {
		cout << "-1" << endl;
	}
	else {
		cout << countNum << endl;
	}

	return 0;
}