BaekJoon 14923번: 미로 탈출(C++)

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

14923번: 미로 탈출

풀이법

1) 방문한 곳을 체크하는 visited배열과 BFS기반의 알고리즘으로 문제를 해결했다.

2) 마법을 사용하여 한 번 벽을 허물 수 있으므로, visited배열을 3차원 배열로 선언하였다. 허물지 않고 진행한 경우 magic이라는 변수를 0으로 한 번 허문 경우는 1로 두어서, 한 번 허물었던 경우 다시 허물고 지나가지 않도록 코드를 작성하였다. (3차원 배열로 작성하지 않는 경우 문제가 발생한다.)

3) queue는 x값, y값, 현재 이동 횟수, 마법 사용 여부를 넣어서 반복을 시켰으며, BFS 기반의 알고리즘이기에 최종 목적지 값이 가장 빨리 나오는 경우가, 가장 최소 이동 횟수가 될 것이기에, 값이 나오는 순간 return 시켰다.

#include <iostream>
#include <algorithm>
#include <queue>
#define INF 987654321
using namespace std;

int m, n;
int hx, hy, ex, ey;
int arr[1001][1001];
bool visited[1001][1001][2];
int vx[4] = { 1,0,0,-1 };
int vy[4] = { 0,1,-1,0 };
void bfs(int a, int b)
{
	queue < pair<int, pair<int, pair<int,int>>>> q;
	visited[a][b][0] = true;
	q.push({ a,{b,{0,0}} });
	while (!q.empty())
	{
		int nowX = q.front().first;
		int nowY = q.front().second.first;
		int cnt = q.front().second.second.first;
		int magic = q.front().second.second.second;
		q.pop();

		if (nowX == ex && nowY == ey)
		{
			cout << cnt;
			return;
		}

		for (int i = 0; i < 4; i++)
		{
			int nextX = nowX + vx[i];
			int nextY = nowY + vy[i];

			if (nextX<1 || nextY<1 || nextX>n || nextY>m)
				continue;
			if (arr[nextX][nextY] == 0 && !visited[nextX][nextY][magic])
			{
				visited[nextX][nextY][magic] = true;
				q.push({ nextX,{nextY,{cnt + 1,magic}} });
			}
			if (arr[nextX][nextY] == 1 && magic==0 && !visited[nextX][nextY][1])
			{
				visited[nextX][nextY][1] = true;
				q.push({ nextX,{nextY,{cnt + 1,1}} });
			}
		}
	}
	cout << -1;
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> m;
	cin >> hx >> hy >> ex >> ey;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> arr[i][j];
	bfs(hx, hy);
}