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

 
#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
#include <tuple>
 
int graph[1001][1001] = {};
bool visit[1001][1001][2] = {};
int iDirX[4] = { 1,-1,0,0 };
int iDirY[4] = { 0,0,1,-1 };
 
int main()
{
	int N = 0;
	int M = 0;
 
	std::cin >> N >> M;
	std::string s = {};
	for (int i = 0; i < N; ++i)
	{
		std::cin >> s;
 
		for (int j = 0; j < M; ++j)
		{
			graph[i][j] = s[j] - '0';
		}
	}
 
	std::queue<std::tuple<int, bool, int, int>> que = {};
	que.push({1, false, 0, 0 });
	visit[0][0][0] = true;
 
	while (!que.empty())
	{
		int iCount = std::get<0>(que.front());
		bool bUse = std::get<1>(que.front());
		int iX = std::get<2>(que.front());
		int iY = std::get<3>(que.front());
		que.pop();
 
		if (iX == N -1 && iY == M - 1)
		{
			std::cout << iCount;
			return 0;
		}
 
		for (int i = 0; i < 4; ++i)
		{
			int iNextX = iX + iDirX[i];
			int iNextY = iY + iDirY[i];
 
			if (iNextX >= 0 && iNextX < N &&
				iNextY >= 0 && iNextY < M)
			{
				if (!graph[iNextX][iNextY] && !visit[iNextX][iNextY][1] && bUse)
				{
					visit[iNextX][iNextY][1] = true;
					que.push({ iCount + 1, bUse, iNextX, iNextY });
				}
 
				else if (graph[iNextX][iNextY] && !visit[iNextX][iNextY][0] && !bUse)
				{
					visit[iNextX][iNextY][1] = true;
					que.push({ iCount + 1, true, iNextX, iNextY });
				}
 
				else if (!graph[iNextX][iNextY] && !visit[iNextX][iNextY][0] && !bUse)
				{
					visit[iNextX][iNextY][0] = true;
					que.push({ iCount + 1, bUse, iNextX, iNextY });
				}
			}
		}
 
	}
 
	std::cout << -1;
	return 0;
}

1. 벽을 뚫을 때와 안뚫을 때를 나눠서 해야한다. ( 나누지 않고 계산을 한다면 벽이 지그재그로 생겼을 때 이미 갈 수 있는 곳을 이미 방문해버려서 못 들어가게 막을 수가 있다. ) 

 

2. 메모리 초과 조심 ( 방문은 무조건 que.push 이전에 해야한다. 그렇지 않으면 그 큐가 오기 전에 같은 곳에 여러 번 방문해서 메모리 초과가 일어난다. )