백준2206(벽부수고이동하기)

jh Seo·2022년 11월 29일

BFS 백준 한번에 못 푼 문제

백준

목록 보기

88/180

개요

백준 2206번: 벽 부수고 이동하기

입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
출력
첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

접근 방식

층을 만들어서 접근을 해야한다는 부분까진 알겠다.
그 후에 0층에서 1층 한번만 갔다가 1층으로 다시 오는걸 구현해보려 했으나
실패했다.
여기저기 찾아본 결과 벽에 막히면 0층에서 1층으로 한번만 이동하고 그후 다른층에서 계속 bfs를 진행하면 되는 것이였다.

따라서 해당 칸의 정보를 담은 구조체를 선언해준 후, 해당 구조체의 큐를 이용해 bfs를 적용했다.

//큐에 넣을 칸 정보들
struct space {
	//행
	int height;
	//열
	int width;
	//벽을 한번 부쉈는지(1) 안 부쉈는지(0)
	bool crushed;
};

그 후, 벽을 만났을때
해당 층이 0층이라면 벽을뚫고 1층으로 가서 bfs를 적용
해당 층이 1층이라면 그대로 bfs를 적용하는식으로 구현했으나, 틀렸다.
-> 찾아보니 둘다 같은 visited배열을 사용해서 틀린 것이였다.
(벽을 뚫은 쪽과 안 뚫은 쪽은 서로 다른 경로로 갈텐데 다른 쪽에서
방문했다고 먼저 체크해버리면 경로가 엉킨다.)
어떤 칸이 벽을 뚫어 1층 배열로 이동할 때, 당연히 1층 배열을 초기화해야한다고 생각했다.
왜냐면 4번 항목과 유사하게 다른 벽을 뚫은 타일들이랑 경로가 겹칠 수 있어서 경로가 엉키는 걱정을 했기 때문이다.

따라서 벽을 만났을 때마다, 해당 좌표에서 visited배열을 복사한 후,
bfs함수를 따로 적용하는 식으로 최단 거리를 구해보려했으나
시간초과가 났다.

-> 고민한 결과 1층 배열끼리는 먼저 1층 배열로 올라온 칸의 경로와 겹쳐도 상관이 없었다.
어차피 해당 경로를 통해 목표 칸으로 도달한다.
먼저 다른 타일의 경로에 왔다면 더 빨리 목적지에 도착한다는 뜻이다.

따라서 벽을 뚫는 순간 1층배열로 보내고 큐에 넣고, 벽을 안 뚫은 경로도 큐에 넣는 식으로 구현했다.
벽을 뚫었을 때, 안 뚫었을 때로 나눠서 더 빨리 도달한게 답이 된다.

//(nextR,nextC)칸에 벽이 있다면
	if (map[nextR][nextC]) {
		//벽을 이미 부신상태면 이제 벽통과 못하므로 continue
		if (crush) continue;
		//벽을 안 부셨다면 1층 visited배열에 방문 체크
		visited[1][nextR][nextC] = true;
		//이 칸은 1층 배열에서 방문체크하며 bfs하면서 놀것
		q.push({ nextR,nextC,1 });
	}

		//(nextR,nextC)칸에 벽이 없다면
				else {
					//벽을 한번 부셨다면 1층 visited배열, 안부셨다면 0층 visited배열에서 체크
					visited[crush][nextR][nextC] = true;
					//조건에 맞는 crush값으로 큐에 들어감
					q.push({nextR, nextC, crush});
				}
			}

코드

#include<iostream>
#include<queue>

using namespace std;

int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
int height = 0, width = 0;
int map[1001][1001];
bool visited[2][1001][1001];

//큐에 넣을 칸 정보들
struct space {
	//행
	int height;
	//열
	int width;
	//벽을 한번 부쉈는지(1) 안 부쉈는지(0)
	bool crushed;
};

void input() {
	char tmp = 0;
	cin >> height >> width;
	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			cin >> tmp;
			//char형으로 받아온 후 하나하나 int값에 넣어줌 
			map[i][j] = tmp - '0';
		}
	}
}


void solution() {
	//같은 지점일때는 그냥 1출력
	if (height == 1 && width == 1) {
		cout << 1;
		return;
	}
	//칸 정보 구조체를 담은 bfs용 큐 선언
	queue<space> q;
	//시작 값인 0,0,false를 넣어준다
	q.push({ 0,0,0 });
	//시작값 방문 처리
	visited[0][0][0] = true;
	//bfs의 각 레벨
	int level = 1;
	//큐가 비어있지 않을 때
	while (!q.empty()) {
		//큐사이즈는 가변적이므로 변수에 할당
		int qSize = q.size();
		for (int i = 0; i < qSize; i++) {
			//큐의 front값
			int r = q.front().height;
			int c = q.front().width;
			bool crush=q.front().crushed;
			//큐 pop()
			q.pop();
			//큐의 front값의 상하좌우칸 반복문을 이용해 표현
			for (int j = 0; j < 4; j++) {
				int nextR = r + dx[j];
				int nextC = c + dy[j];
				//만약 범위 바깥이면 바로 continue
				if (nextR < 0 || nextC < 0 || nextR >= height || nextC >= width) continue;
				//이미 방문한 지역이면 continue
				if (visited[crush][nextR][nextC]) continue;
				//목표지점이면 시작지점도 포함이므로 level+1값 출력
				if (nextR == height - 1 && nextC == width - 1) {
					cout << level + 1;
					return;
				}
				//(nextR,nextC)칸에 벽이 있다면
				if (map[nextR][nextC]) {
					//벽을 이미 부신상태면 이제 벽통과 못하므로 continue
					if (crush) continue;
					//벽을 안 부셨다면 1층 visited배열에 방문 체크
					visited[1][nextR][nextC] = true;
					//이 칸은 1층 배열에서 방문체크하며 bfs하면서 놀것
					q.push({ nextR,nextC,1 });
				}
				//(nextR,nextC)칸에 벽이 없다면
				else {
					//벽을 한번 부셨다면 1층 visited배열, 안부셨다면 0층 visited배열에서 체크
					visited[crush][nextR][nextC] = true;
					//조건에 맞는 crush값으로 큐에 들어감
					q.push({nextR, nextC, crush});
				}
			}
		}
		level++;
	}
	//반복문 빠져나왔다면 
	cout << -1;

}

int main() {
	input();
	solution();
}