BaekJoon-no.2206 벽 부수고 이동하기

int arr[1000][1000];
int check[2][1000][1000]; //상태 2개 저장

int dy[4] = {1,0,-1,0};
int dx[4] = {0,1,0,-1};

struct info{
	int y,x,s;
};

int m,n;
void bfs(int y,int x,int status){ //status = 0 벽아직 안뚫, = 1 뚫
	queue<info> q;
	info in;
	in.y = y;
	in.x = x;
	in.s = status;

	q.push(in);

	check[status][y][x] = 1;

	while(!q.empty()){
		info cur = q.front();
		q.pop();
		int y = cur.y;
		int x = cur.x;
		int s = cur.s;

		for(int i=0;i<4;i++)
		{
			int nexty = y + dy[i];
			int nextx = x + dx[i];

			if(0<= nexty && nexty <n && 0 <= nextx && nextx < m)
			{
				if(arr[nexty][nextx] == 1 && s == 0)//벽을 부수지 않은 상태에서 벽을 만나면 부순다.
					//다른 부수지 않는 노드에 의해서 다시 부서져도 최단경로를 찾기 때문에 에러 X
				{
					check[1][nexty][nextx] = check[0][y][x] + 1;

					info next;
					next.y = nexty;
					next.x = nextx;
					next.s = s + 1;

					q.push(next);

				}
				else if(arr[nexty][nextx] == 0 && check[s][nexty][nextx] == 0)
				{
					//벽이 아니라면 상태를 유지하며 계속 진행
					info next;
					next.y = nexty;
					next.x = nextx;
					next.s = s;

					q.push(next);

					check[s][nexty][nextx] = check[s][y][x] + 1;

				}
			}
		}
	}
	return ;
}