[골3] 2206 - 벽 부수고 이동하기 (최신화)

3차원 배열 / 메모리 많이 차지함

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>	
#include <map>
#include <set>

using namespace std;
using ll = long long;

#pragma region 상하좌우 / 위치

const pair<int, int> dir[]
{
	{  1,  0 },
	{ -1,  0 },
	{  0, -1 },
	{  0,  1 },
};

#define _y first
#define _x second

#pragma endregion

#pragma region 빠른 입출력

#define FAST_IO() \
{\
	ios::sync_with_stdio(false);\
	cin.tie(NULL); \
	cout.tie(NULL); \
}\

#pragma endregion

#define MAX 1001

struct sNode
{
	int y, x, depth;
	bool isBlock;
};

vector<vector<int>> graph;
int vis[MAX][MAX][2];
int n, m;

int bfs()
{
	queue<sNode> q;
	q.push({ 0, 0, 1, false });
	vis[0][0][0] = true;

	while (!q.empty())
	{
		auto cur = q.front();
		q.pop();
		int y = cur.y, x = cur.x, depth = cur.depth;
		bool isBlock = cur.isBlock;

		if (y == n - 1 &&
			x == m - 1)
			return depth;

		// 4선 방향으로 bfs
		for (int i = 0; i < 4; i++)
		{
			int ny = y + dir[i].first, nx = x + dir[i].second;

			// 범위 체크
			if (ny >= n ||
				ny < 0 ||
				nx >= m ||
				nx < 0)
				continue;

			if (vis[ny][nx][isBlock])
				continue;

			// 아직 안뚫린 벽
			if (graph[ny][nx])
			{
				if (!isBlock)
				{
					vis[ny][nx][1] = true;
					q.push({ ny, nx, depth + 1, true });
				}
			}
			else
			{
				vis[ny][nx][isBlock] = true;
				q.push({ ny, nx, depth + 1, isBlock });
			}
		}
	}
	return -1;
}

int main()
{
	FAST_IO();

	cin >> n >> m;
	graph.resize(n, vector<int>(m));

	for (int i = 0; i < n; i++)
	{
		string val;
		cin >> val;

		for (int j = 0; j < m; j++)
			graph[i][j] = val[j] - '0';
	}
	cout << bfs();
}

2차원 vector 

#pragma region 라이브러리

#include <iostream>
#include <cmath>
#include <string>
#include <functional>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

#pragma endregion

#pragma region 최적화용

#define FAST_IO() ios::sync_with_stdio(0); cin.tie(0);
#define y first
#define x second

using IntPair = pair<int, int>;

// 상하좌우
IntPair dir[]
{
	{ 1, 0 },
	{-1, 0 },
	{ 0, -1 },
	{ 0, 1 }
};

#pragma endregion

struct sNode
{
	int y, x, depth;
	bool isBlock;

	sNode(int y, int x, int depth, bool isBlock) : y(y), x(x), depth(depth), isBlock(isBlock)
	{

	}
};

vector<vector<int>> board;
vector<vector<bool>> vis[2];
IntPair des;

int BFS()
{
	queue<sNode> q;
	q.push({ 0, 0, 1, false });
	vis[0][0][0] = true;

	while (!q.empty())
	{
		auto cur = q.front(); q.pop();
		int depth = cur.depth;
		bool isBlock = cur.isBlock;

		if (cur.y == des.y - 1 &&
			cur.x == des.x - 1)
			return depth;

		for (int i = 0; i < 4; i++)
		{
			int ny = cur.y + dir[i].y, nx = cur.x + dir[i].x;

			// 범위 체크
			if (ny < 0 ||
				ny >= des.y ||
				nx < 0 ||
				nx >= des.x)
				continue;

			if (vis[isBlock][ny][nx])
				continue;

			// 아직 안뚫린 벽
			if (board[ny][nx])
			{
				if (!isBlock)
				{
					vis[1][ny][nx] = true;
					q.push({ ny, nx, depth + 1, true });
				}
			}
			else
			{
				vis[isBlock][ny][nx] = true;
				q.push({ ny, nx, depth + 1, isBlock });
			}
		}
	}
	return -1;
}

int main()
{
	FAST_IO();

	cin >> des.y >> des.x;
	board.resize(des.y, vector<int>(des.x));
	vis[0].resize(des.y, vector<bool>(des.x));
	vis[1].resize(des.y, vector<bool>(des.x));

	// 띄어쓰기 없이 입력 받으니 string으로
	for (int y = 0; y < des.y; y++)
	{
		string str;
		cin >> str;

		for (int x = 0; x < des.x; x++)
			board[y][x] = str[x] - '0';
	}
	cout << BFS() << endl;
}