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

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

2206번: 벽 부수고 이동하기

2206번 제출 맞은 사람 숏코딩 풀이 풀이 작성 풀이 요청 재채점/수정 채점 현황 강의 벽 부수고 이동하기 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 192 MB 22689 5172 3222 23.100% 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작...

www.acmicpc.net

​

​

일반 bfs인데, 배열에 벽을 부쉈는지 여부(wall)가 추가된다.

​

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <tuple>
using namespace std;
queue<tuple<int,int,int>> q;
tuple<int, int, int>p;
int arr[1001][1001];
int check[1001][1001][2];
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &arr[i][j]);
		}
	}
	//cout<<endl;
	q.push({ 0,0,0 });
	check[0][0][0] = 1;
	while (!q.empty()) {
		p = q.front();
		q.pop();

		//for (int i = 0; i < n; i++) {
		//	for (int j = 0; j < m; j++) {
		//		cout << check[i][j][get<2>(p)]<<"\t";
		//	}
		//	cout << endl;
		//}
		//cout << endl;
		if (get<1>(p) == m - 1 && get<0>(p) == n - 1) {
			cout << check[n-1][m-1][get<2>(p)];
			return 0;
		}
		for (int i = 0; i < 4; i++) {
			int nx = get<1>(p) + dx[i];
			int ny = get<0>(p) + dy[i];
			int wall = get<2>(p);

			if (0 <= nx && nx < m && 0 <= ny && ny < n&&check[ny][nx][wall]==0) {
				if (arr[ny][nx] == 0) {
					check[ny][nx][wall] = check[get<0>(p)][get<1>(p)][wall] + 1;
					q.push({ ny,nx,wall });
				}
				else if (arr[ny][nx] == 1) {
					if (wall == 0) {
						check[ny][nx][1] = check[get<0>(p)][get<1>(p)][wall] + 1;
						arr[ny][nx] = 0;
						q.push({ ny,nx,1 });

					}
				}
			}
		}
	}
	cout << -1;
	return 0;
}