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

문제

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

2206번: 벽 부수고 이동하기

 

문제풀이

처음에 DFS로 풀었는데 계속 시간 초과가 뜨길래 질문을 보니 가중치 없는 최단거리는 BFS로 풀어야 된다는 글을 봤다.

https://www.acmicpc.net/board/view/27386

그래서 코드를 지우고 다시 BFS로 풀었다.

다음 칸을 갈 때 방문했으면 현재 거리가 최단거리일 때만 다음칸으로 이동하고,

방문을 하지 않은 칸이라면 방문을 하게 했다.

그런데 이렇게 풀면 틀렸습니다가 나온다.

이미 벽을 부쉈는데, 현재 위치에서 도착지점까지 무조건 벽을 한번 부숴야 되는 경우가 있기 때문이다.

그렇기 때문에 벽을 부숴서 온 거리가 훨씬 짧더라도 벽을 부수고 오지 않고 온 경우도 생각해야 된다.

아래 써놓은 예가 그런 경우이다.

8 8
01000100
01010100
01010100
01010100
01010100
01010100
01010100
00010100

답 29

 

int BFS() {
	queue<vector<int>>q; // q는 (y좌표, x좌표, 부쉈는지 여부, 거리)로 구성한다.
	q.push({ 1,1,1,1 }); // smash가 1이면 벽을 부술 수 있다는 뜻이고
	while (!q.empty()) { // 0이면 이미 부숴서 더 이상 부술 수 없는 뜻이다.
		int y = q.front()[0];
		int x = q.front()[1];
		int smash = q.front()[2];
		int dis = q.front()[3];
		q.pop();
		if (y == N && x == M) return dis; // 도착지점에 도착하면 거리를 return 한다.
		for (int cnt = 0; cnt < 4; ++cnt) { // 상하좌우 방향 총 4방향
			int n_y = y + dy[cnt];
			int n_x = x + dx[cnt];
			if (n_y >= 1 && n_y <= N && n_x >= 1 && n_x <= M) { // 범위를 벗어나지 않으면
				if (visit[n_y][n_x] == 1 && smash == 1) { // 이미 방문을 했으나 벽을 부수지 않았을 때
					if (matrix[n_y][n_x] == 0) { // 벽이 없을 때
						visit[n_y][n_x] = 2; // 벽을 부수지 않고 온 경우로 한 번만 저장하게 한다.
						q.push({ n_y, n_x,1, dis + 1 }); // 벽을 부수지 않고 온 경우도 q에 push 해야 한다.
					}
					else { // 벽이 있을 때, 벽을 부순다.
						visit[n_y][n_x] = 2;
						q.push({ n_y, n_x, 0, dis + 1 });
					}

				}
				else if (visit[n_y][n_x] == 0) { // 방문하지 않았을 때
					visit[n_y][n_x] = 1; // 방문 표시
					if (matrix[n_y][n_x] == 1) {
						if (smash == 1)
							q.push({ n_y, n_x,0, dis + 1 });
					}
					else {
						q.push({ n_y, n_x, smash, dis + 1 });
					}
				}
			}
		}
	}
	return -1; // 큐가 비면 도착하지 못했단 뜻이므로 -1을 return 한다.
}

 

 

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int N, M;
vector<vector<int>>matrix;
vector<vector<int>>visit;
vector<int> dx = { -1,1,0,0 };
vector<int> dy = { 0,0,1,-1 };
int dis = 1;

int BFS() {
	queue<vector<int>>q;
	q.push({ 1,1,1,1 });
	while (!q.empty()) {
		int y = q.front()[0];
		int x = q.front()[1];
		int smash = q.front()[2];
		int dis = q.front()[3];
		q.pop();
		if (y == N && x == M)	return dis;
		for (int cnt = 0; cnt < 4; ++cnt) {
			int n_y = y + dy[cnt];
			int n_x = x + dx[cnt];
			if (n_y >= 1 && n_y <= N && n_x >= 1 && n_x <= M) {
				if (visit[n_y][n_x]==1&&smash==1) {
					if (matrix[n_y][n_x] == 0) {
						visit[n_y][n_x] = 2;
						q.push({ n_y,n_x,1,dis + 1 });
					}
					else {
						visit[n_y][n_x] = 2;
						q.push({n_y, n_x, 0, dis + 1});
					}

				}
				else if (visit[n_y][n_x]==0) {
					visit[n_y][n_x] = 1;
					if (matrix[n_y][n_x] == 1) {
						if (smash == 1)
							q.push({ n_y,n_x,0,dis + 1 });
					}
					else {
						q.push({ n_y,n_x,smash,dis + 1 });
					}
				}

			}
		}
	}
	return -1;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	bool smash = true;
	string number = "";
	int y = 0, x = 0;
	cin >> N >> M;

	matrix.resize(N + 1, vector<int>(M + 1, 0));
	visit.resize(N + 1, vector<int>(M + 1, 0));

	for (y = 1; y <= N; ++y) {
		cin >> number;
		for (x = 1; x <= M; ++x) {
			matrix[y][x] = number[x - 1] - '0';
		}
	}

	cout << BFS();
}