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

 

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

---

문제

---

접근 방법

 

BFS를 통해 문제를 해결하였다.

중요한점은 벽을 부술 수 있는 경우가 딱 한번 있다는 점이다.

따라서 다른 BFS 문제들과 다르게 해당 경우가 벽을 부수고 들어간 경우인지, 아닌지를 구분을 해야한다.

벽을 부수고 들어간 경우일 때, 벽을 만나면 더 진행을 못하지만, 벽을 부수고 들어간 경우가 아니라면 벽을 만나도 한번 통과가 가능하다.

이러한 구분은 큐에 위치값(x,y)이외에도 큐에 들어온 경우가 벽을 부쉈는지, 아닌지 구분할 bool 변수까지 포함을 시키면 된다.

 

따라서 큐에서 상하좌우를 판별할때

• 벽을 이미 부수고 들어왔을 경우

상하좌우 벽을 부순 상황에서 한번도 방문을 안 했고, 벽이 아닐 때의 x,y값과 벽을 이미 부쉈다는 true값을 큐에 넣는다.

• 여태껏 벽을 부수지 않고 들어왔고, 다음 방문 지점이 벽이 아닐 경우

다음 방문 지점이 벽을 부수지 않은 상황에서 한번도 방문을 안 했다면,  x,y값과 벽을 아직 안 부쉈다는 false값을 큐에 넣는다.

• 여태껏 벽을 부수지 않고 들어왔고, 다음 방문 지점이 벽일 경우

다음 방문 지점이 벽을 부순 상태에서 한번도 방문을 안 했다면, 큐에 x,y값과 벽을 부쉈다는 true값을 큐에 넣는다.

 

이러한 방식으로 큐에 원소가 없어질때까지 반복해주면, 모든 정점에 관해 

1. 벽을 한번도 부수지 않은 상태에서의 최단 경로
2. 벽을 한번 부순 상태에서의 최단경로

를 구할 수 있게 된다.

 

주의사항

 

예외처리를 몇가지를 해야하는데, 목표 지점에 두가지 방식으로 모두 도착이 가능하다면 둘 중 더 작은값을 출력,

한가지 방식으로만 도착을 했다면 그 방식으로 구한 값을 출력,

두 방식 모두 도착을 못 했다면 -1을 출력한다.

또한 , 행과 열의 크기가 1,1이면 해당 위치가 벽이든 아니든 무조건적으로 목표 위치로 도달이 가능하기 때문에 1을 출력해준다.

 

---

코드

#include<iostream>
#include<queue>
#include<string>
#include<algorithm>
#include<tuple>
using namespace std;
int n, m;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int arr[1001][1001];
int counter[1001][1001][2];
bool flag[1001][1001][2]; 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	string k;
	for (int i = 1; i <= n; i++) {
		cin >> k;
		for (int j = 1; j <= m; j++) {
			arr[i][j] = k[j-1]-48; 
		}
	}
	queue<tuple<int, int, bool>> q;
	q.push({ 1,1,false });
	while (!q.empty()) {
		int x = get<0>(q.front());
		int y = get<1>(q.front());
		bool b = get<2>(q.front());
        //b가 true라면 여기까지 오는데 벽을 부순경우,false라면 아직 부수지 않은 경우
		q.pop();
		for (int i = 0; i < 4; i++) {
			int x2 = x + dx[i];
			int y2 = y + dy[i];
			if (x2 > 0 && y2 > 0 && x2 <= n && y2 <= m) {			
				if (b) {
					if (arr[x2][y2] == 0 && !flag[x2][y2][1]) {
						flag[x2][y2][1] = true;
						counter[x2][y2][1] = counter[x][y][1] + 1;
						q.push({ x2,y2,true });
					}
				}
				else {
					if (arr[x2][y2] == 1 && !flag[x2][y2][1]) {
						flag[x2][y2][1] = true;
						counter[x2][y2][1] = counter[x][y][0] + 1;
						q.push({ x2,y2,true });
					}
					if (arr[x2][y2] == 0 && !flag[x2][y2][0]) {
						flag[x2][y2][0] = true;
						counter[x2][y2][0] = counter[x][y][0] + 1;
						q.push({ x2,y2,false });
					}
				}
			}
		}
	}
	if (n == 1 && m == 1)cout << 1; //행과 열 크기가 모두 1일경우 무조건 1번에 도착 가능
	else {
		if (counter[n][m][0] != 0 && counter[n][m][1] != 0) {
        //두가지 방식으로 모두 도착이 될 경우
			cout << min(counter[n][m][0], counter[n][m][1]) + 1;
		}
		if (counter[n][m][0] == 0 && counter[n][m][1] != 0) { 
        //벽을 부순 경우만 도착했을 경우
			cout << counter[n][m][1] + 1;
		}
		if (counter[n][m][0] != 0 && counter[n][m][1] == 0) {
        //벽을 부수지 않을 때만 도착했을 경우
			cout << counter[n][m][0] + 1;
		}
		if (counter[n][m][0] == 0 && counter[n][m][1] == 0) {
        //두 방식 모두 도착하지 못 할 경우
			cout << -1;
		}
	}
}

---

결과

BFS를 이용한 문제였다.