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

BFS문제입니다.

1,1에서 N,M까지 가는데 최단 경로를 구하는 문제입니다.
0은 이동할 수 있는 곳이고, 1은 얼음으로 이동할 수 없습니다.
가는 도중에 얼음을 최대 한개까지 깨고 이동할 수 있습니다.

큐<벡터<int>>에 현재 위치와 경로 거리, 얼음을 깼는지의 여부를 저장해두었습니다.
얼음을 깼는지 여부에 따라서 BFS를 돌면서 얼음을 만났을 때
얼음을 부수고 가는 경우에 대해서도 체크할 수 있었습니다.

 

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

int n, m;
int countNum = MAX;
int map[1010][1010];
int visit[1010][1010][2];
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);
			}
			if (map[x][y] == 1 && d == 0) {
				vector<int> element;
				element.push_back(x);
				element.push_back(y);
				element.push_back(c + 1);
				element.push_back(1);
				q.push(element);
			}
			if (abs(map[x][y]) != 1 && visit[x][y][d] == 0) {
				
				visit[x][y][d] = 1;
				vector<int> element;
				element.push_back(x);
				element.push_back(y);
				element.push_back(c + 1);
				element.push_back(d);
				q.push(element);
			}
		}
	}
	return;
}

int main(int argc, char* argv[])
{
	int k = 2;
	string s;
	
	cin >> n >> m;

	memset(map, -1, 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;
}