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

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 (0, 0)에서 출발해 (N-1, M-1)에 가장 빨리 도착하는 최단경로를 구하는 문제다.

 

이 문제에서 중요한 점은 경로 중간에 벽이 있는 경우에는 벽을 부수고 이동할 수 있다는 점이다.

 

일단, 최단경로를 구하기 위해서는 BFS를 이용해 특정 지점에 처음 도달했을 경우에 이동한 칸수가 정답이다.

 

하지만 이 문제에서는 벽을 부술 수 있기 때문에 이를 고려해야 한다.

 

그러므로 특정 지점에 방문했을 때, 벽을 부수고 방문했는지와 벽을 부수지 않고 방문했는지를 구분해서 저장해 준다.

 

이를 위해 visited의 2차원 vector에 벽을 부수고 방문한 경우, 부수지 않고 방문하는 경우의 2가지 경우를 고려해 [2*N*M] 크기의 visited vector를 만들었다.

 

다른 BFS문제와 마찬가지로 이동할 수 있는 4 방향 (상, 하, 좌, 우)으로 이동하고, 이동해 방문한 칸이 벽을 한번이라도 부수고 도착했는지, 벽을 한번도 부수지 않고 도착했는지를 구분해 문제를 풀면 된다.

 

 

​

[아이디어 정리]

1. 벽을 부수고 방문하는 경우, 부수지 않고 방문하는 경우와 N * M 칸이 있으므로 [2*N*M]의 visited 배열을 만든다.
2. 이동한 곳이 벽일 경우에 아직 벽을 한 번도 부수지 않았다면, 벽을 부수고 방문한다.
3. 만약 벽을 한 번이라도 부쉈다면, 방문할 수 없다.
4. 이동한 곳이 벽이 아닐 경우에는 그냥 방문한다.
5. (N-1, M-1)에 도달했다면 그 경우가 최단경로이므로 움직인 칸의 수를 출력한다.

 

 

 

Code

 

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N, M;
	cin >> N >> M;
	vector<string> mm(N);
	vector<vector<vector<int>>> visited(2,vector<vector<int>>(N, vector<int>(M,-1)));
	for (int i = 0; i < N; i++) 
	{
		cin >> mm[i];
	}
	visited[0][0][0] = 1;
	queue<vector<int>> q;
	vector<int> nv(4, 0);
	nv[2] = 1;
	vector<int> temp;
	temp = nv;
	q.push(nv);
	int ny, nx, t=0;
	while (!q.empty()) 
	{
		nv = q.front();
		if (nv[0] == N - 1 && nv[1] == M - 1) 
		{
			t = nv[3]; // 단지 변수 저장용
			break;
		}
		q.pop();
		temp[2] = nv[2] + 1;
		for (int i = 0; i < 4; i++) 
		{
			ny = nv[0] + dy[i];
			nx = nv[1] + dx[i];
			if (ny >= 0 && ny < N && nx >= 0 && nx < M) 
			{
				temp[0] = ny, temp[1] = nx;
				if (mm[ny][nx] == '1'&&visited[1][ny][nx]==-1) //방문한 적이 없다면
				{
					if (nv[3] == 0)
					{
						temp[3] = 1;
						q.push(temp);
						visited[1][ny][nx] = temp[2];
					}
				}
				else if (mm[ny][nx] == '0' && visited[nv[3]][ny][nx] == -1)
				{
					temp[3] = nv[3];
					visited[nv[3]][ny][nx] = temp[2];
					q.push(temp);
				}
			}
		}
	}
	cout << visited[t][N-1][M-1];
	return 0;
}

 

---

벽을 부수고 방문한 경우와 부수지 않고 방문한 경우만 구분하면 다른 BFS와 똑같이 풀 수 있는 문제였다.

 

 

 

2206번: 벽 부수고 이동하기