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

---

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• BFS

---

문제 설명

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

---

입력 설명

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

---

출력 설명

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

---

예제 입력

6 4
0100
1110
1000
0000
0111
0000

4 4
0111
1111
1111
1110

---

예제 출력

15

-1

---

아이디어

queue에 x좌표 y좌표 현재까지 이동한 칸 수, 벽 부수기 사용 유무를 저장하고

3차원 visited 행렬을 선언하여 벽을 부순 visited와 벽을 부수지 않은 visited를 구분하여 기록한다. 

 

---

알고리즘

BFS를 진행하는데 queue에 x좌표, y좌표, 현재까지 이동 거리, 벽 부수기 사용 유무를 push 한다.

만약 q에서 꺼낸 좌표의 가 x==n이면서 y==m이라면 현재까지의 이동 거리를 출력한다.

만약 q에서 꺼낸 좌표의 값이 2이거나 visited==true라면 넘어간다.

이후 visited를 true로 바꿔준다.

이후 인접한 칸이 값이 0이거나 1이지만 벽 부수기를 사용하지 않은 상태라면 q에 넣어준다.

n, m에 도달하지 못했다면 -1을 출력한다.

---

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
using namespace std;
int n, m, dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};
void BFS(vector<vector<int>> &vec, vector<vector<vector<bool>>> &visited)
{
	queue<tuple<int,int,int,bool>> q;
	q.push(make_tuple(1,1,1,false));
	while(!q.empty())
	{
		int x = get<0>(q.front());
		int y = get<1>(q.front());
		int c = get<2>(q.front());
		bool b = get<3>(q.front());
		q.pop();
		if(x == n && y == m) {
			cout<<c;
			return;
		}
		else if(vec[x][y] == 2 || visited[x][y][b]) continue;
		visited[x][y][b] = true;
		for(int i=0; i<4; i++)
		{
			int nx = x+dx[i], ny = y+dy[i];
			if(vec[nx][ny] == 0) q.push(make_tuple(nx,ny,c+1,b));
			if(vec[nx][ny] == 1 && b == false) q.push(make_tuple(nx,ny,c+1,true));
		}
	}
	cout<<-1;
}
int main()
{
	cin>>n>>m;
	vector<vector<vector<bool>>> visited(n+1,vector<vector<bool>>(m+1, vector<bool>(2,false)));
	vector<vector<int>> vec(n+2, vector<int>(m+2,2));
	for(int i=1; i<=n; i++)
	{
		string str; cin>>str;
		for(int j=0; j<m; j++) vec[i][j+1] = str[j]-48;
	}
	BFS(vec, visited);
	return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/2206

그냥 단순하게 BFS를 사용해서 풀려고 시도했지만 계속해서 틀렸다.

단순한 BFS를 사용하면 틀리는 이유는 벽을 한 번 부수고 갈 수 있기 때문에

벽 부수기를 언제 사용하는지에 따라서 벽 부수기를 안 쓰는 것보다 더 빠르게 가는 경우가 존재한다.

그렇기 때문에 벽 부수기를 미리 사용하면 필요할 때 쓰지 못할 수 있다.

따라서 3차원 visited 배열을 사용하여 벽을 부쉈을 때와 벽을 부수지 않았을 때의 방문을 별도로 기록해서 해결했다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!