2206 벽부수고이동하기

문제링크

😊 코드 설명

현재상태를 계속해서 큐에 집어넣어주고 벽을 부쉈는지에대한 visit배열을 한차원 늘려서 확인해준다.

이외의 중요팁들은 백준 게시판에서 글을 가져와보았다.

😊 코드

#include<iostream>
#include<queue>
#include<vector>
#include<string>
using namespace std;
int N, M;
int map[1000][1000];
bool visited[1000][1000][2]; //벽을부순횟수[2] 기록
//벽을부수고왔는지 안부수고왔는지 다른 경로가 되기때문에 visit 3차원 필요!!
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };
struct ABC {
	int time;
	int y;
	int x;
	int wall;
};
void bfs(int y, int x) {
	queue<ABC> q;
	q.push({ 1,y,x,0 }); //시작 1초
	visited[y][x][0] = true;

		while (!q.empty()) {
			

			int y = q.front().y;
			int x = q.front().x;
			int time = q.front().time;
			int wall = q.front().wall;//벽부쉈는지 아닌지 기록용
			q.pop();
			if (y == N - 1 && x == M - 1) {
				cout << time;
				return;
			}

			
			for (int i = 0; i < 4; i++) {
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
				
				if (!visited[ny][nx][wall] && map[ny][nx] == 1 && wall==0) {//
					
					q.push({ time + 1,ny,nx,wall+1 });
					visited[ny][nx][wall+1] = true; //wall=1 이아닌 wall+1을통해 매개변수로 접근해야한다.(다시 돌아오는 경우의수 생각)
				}
				
				 else if (!visited[ny][nx][wall] && map[ny][nx] == 0) { //wall==0일수도 wall ==1 일수도 
					q.push({ time + 1,ny,nx,wall });
					visited[ny][nx][wall] = true;
				}

			}


	 	}
	
	cout << -1;
	return;

}
int main() {
	cin >> N >> M;
	
	for (int y = 0; y < N; y++) {
		string abc;
		cin >> abc;
		for (int x = 0; x < M; x++) {
			int temp=abc[x] - '0';
			map[y][x] = temp;
		}
	}

	
	bfs(0, 0);


	return 0;
}