[C++][Baekjoon][BFS 탐색] 2206번 벽 부수고 이동하기 상세 해설

[문제]

 

2206번: 벽 부수고 이동하기

N×M의 행렬로 표현된 맵에서 (1, 1)에서 (N, M)까지 이동할 때 걸리는 최단 경로를 구하는 문제.

이 때, 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타내며 1회에 한하여 벽을 부수고 이동할 수 있다.

 

[풀이]

Break 유무를 저장해놓고 한번도 깬 적 없는 벽을 깨가면서 탐색해야 할 것 같은데 그 구조를 못짜겠어서 한참을 헤맸다.

결국 풀이 참조...

 

이 문제의 핵심은 탐색한 경로를 queue에 저장할 때, 벽을 부순 경로인지 벽을 부수지 않은 경로인지도 저장해줘야 한다는 점이다. 또한, 탐색한 경로를 방문체크할 때 벽을 부순 적이 있으면서 방문할 수도 있고 벽을 부순적이 없으면서 방문할 수도 있기 때문에 두 가지 경우의 수를 모두 열어두고 한 경우만 방문 체크해줘야한다는 점이다.

 

이 때, 벽을 부순 적이 있다면 벽이 아닌 경로를 계속해서 이동하면 되고, 벽을 부순 적이 없다면 벽과 벽이 아닌 곳 모두  이동가능하다.

 

즉, 각 점들은 좌표와 벽을 부순 횟수, 이동 횟수 정보를 갖고 있어야 한다. 이동 횟수 정보는 최단경로길이를 찾아야하기 때문에 저장해줬다. 탐색할 때마다 +1씩해서 경로 길이를 찾는다.

class Point {
public:
	int x;
	int y;
	int breakCount;//벽을 부순 횟수. 0 or 1로 표현
	int count;//이동 횟수. 나중에 출력해줘야 함.
	Point(int x, int y, int breakCount, int count) {
		this->x = x;
		this->y = y;
		this->breakCount = breakCount;
		this->count = count;
	}
};

그리고 벽을 뚫은 적이 있는 경로가 방문체크를 하며 탐색하는 경우와 벽을 뚫은 적 없는 경로가 방문체크하며 탐색하는 경우. 2가지로 나뉘기 때문에 visited  배열을 2개 만들어줘야 한다. 그 배열은 3차원 행렬로 표현했다. 벽을 뚫은 적 없으면서 방문했다면 visited[x][y][0] = true로, 벽을 뚫은 적 있으면서 방문했다면 visited[x][y][1] = true 로 체크할 거다.

bool visited[MAX_VALUE][MAX_VALUE][2] = { false, };

 

 

여기서 질문이 있을 것이다. (나도 계속 이해가 안갔던 부분!!) 벽을 뚫을 때, 항상 최선이 되는 경우를 뚫어야 할 텐데, 앞에서 뚫은 경우보다 뒤에서 뚫은 경우가 더 최선이면 어떡하지????

 

결론은 상관없다 !!! 뒤에 나오는 최선의 경우는 벽을 뚫은 적 없는 경로가 재탐색해줄 것이기 때문이다 !!!!!

아래 예제를 보며 이해해보자.

 

예제 1번을 풀어보면 다음과 같다.

queue에 저장되는 인자 3개는 Point정보를 의미하는데 순서대로 Point(x좌표, y좌표, 벽을 부순 횟수)이다.

즉, 맨 처음에 큐에 저장되는 값은 x좌표 1, y좌표 1, 벽을 부순 횟수 0을 저장한다.

 

그리고 (1, 1)부터 오른쪽, 아래, 왼쪽, 위 순으로 주변을 탐색한다.

(1, 1) 주위 좌표인 (1, 2)와 (2, 1)을 탐색하는데, 아직 벽을 부순 횟수가 0이므로 벽을 만났을 때 벽을 부술 수 있다.

따라서 벽을 부수고 다음 경로로 이동할 것이다. 즉, visited[1][2][1] = visited[2][1][1] = true로 방문 체크해주고 queue에 Point(1, 2, 1)과 Point(2, 1, 1)을 넣는다.

 

다음 queue의 맨 앞에 있는 Point(1, 2, 1)을 꺼내서 탐색을 진행할 건데,

이미 앞에서 벽을 부순 적이 있으므로(3번째 인자가 1이므로) 다음 경로에선 벽이 아닌 경로(map[x][y] = 0)만 탐색이 가능하다. 그리고 벽을 부순 적이 있으므로 breakedCount를 +1 해준 상태인 Point(1, 3, 1) 를 queue에 저장하고 벽을 부수고 방문했다는 표시로 visited[1][3][1] = true로 방문 체크 해준다.

그 뒤로도 벽을 부술 수 있는 횟수가 0이므로 벽이 아닌 경로만 탐색하며 (N, M) 좌표에 도달할 것이다.

 

다른 예제도 살펴보자.

위 예제는 맨 처음부터 벽을 뚫지 않는다. 벽을 뚫거나 뚫지 않으면서 N x M 위치까지 가는 거다.

 

Point(1, 1, 0) 좌표를 탐색하고, Point(1, 2, 0) 좌표와 Point(2, 1, 0) 좌표를 큐에 넣는다. 그리고 visited[1][2][0] = visited[2][1][0] = true로 방문 체크한다. 아직 벽을 뚫은 적이 없으므로 두 좌표 모두 3번째 인자(벽을 뚫은 횟수)는 0이이고 벽을 뚫지 않고 이동한 경로에 방문체크해주는 거다.

 

다음 queue의 제일 앞에 있는 좌표인 Point(1, 2, 0)를 탐색하자. 이 때는 (1, 3)좌표와 (2, 2)좌표를 탐색할 수 있는데, (1, 3)좌표로 이동할 경우는 벽을 뚫지 않고 이동할 수 있고, (2, 2)좌표로 이동할 때는 벽을 뚫어야만 이동 가능 하다. Point(1, 2, 0) 값의 3번째 인자를 통해 이 경로는 벽을 뚫은 적이 없으므로 두 좌표 모두 queue에 저장한다. 이 때, (1, 3)으로 이동하는 경로는 벽을 뚫은 적 없으므로 Point(1, 3, 0)의 값을, (2, 2)로 이동하는 경로는 벽을 뚫어야 하므로 Point(2, 2, 1)로 표현 및 queue에 저장한다. 그리고 visited[1][3][0] = visited[2][2][1] =  true 로 각각 벽을 뚫은 적 없으면서 방문한 경로와 벽을 뚫으면서 방문한 경로를 방문체크해준다.

다음 queue의 맨 앞의 값인 Point(2, 1, 0)을 탐색하자. Point(2, 1, 0)의 값을 보면 알 수 있드시 지금까지 벽을 뚫은 적없는 경로를 저장한 것이다. 아직 벽을 뚫은 적이 없으므로 (2, 2)좌표와 (3,1)좌표 모두 가능할 텐데, (2, 2) 좌표로 이동할 경우 벽을 뚫은 적 있다는 표시를 해줘야 한다. Point(2, 2, 1) 이렇게. 근데 (2, 2, 1)은 이미 (1, 2)좌표에서 탐색할 때 visited[2][2][1] = true로 체크해주고 queue에 넣어줬다. 따라서 이미 이번 경로에서는 Point(3, 1, 0)만 저장하고 벽을 뚫은 적 없으면서 방문했다는 표시로 visited[3][1][0] = true 로 체크해준다.

 

그 다음은 Point(1,3,0)를 탐색한다. (1, 4) 좌표와, (2, 3) 좌표를 탐색할 텐데, (1, 4)좌표는 벽이 아닌 경로를 체크하는 배열에 방문체크해주고, (2, 3)좌표는 벽을 뚫어야 하므로 벽인 경로를 체크하는 배열에 방문체크해준다. 즉 visited[1][4][0] = visited[2][3][1] = true이고, queue에 Point(1, 4, 0)과 Point(2, 3, 1) 값이 저장된다.

Point(2, 2, 1)은 벽을 부순 적 있는 이동경로 이므로 visited[2][3][1] = visited[3][2][1]= true로 체크해주고, Point(2, 3, 1)과 Point(3, 2, 1)을 queue에 넣는다.

 

Point(3, 1, 0)은 벽을 부순 적 없는 이동경로 이므로 visited[3][2][0] = visited[4][1][0] = true로 체크해주고 queue에 Point(3, 2, 0)과 Point(4, 1, 0)을 넣어준다.

 

여기서 queue에 Point(3, 2, 1)과 Point(3, 2, 0)이 있는 것이 보일 것이다. 이렇게 벽을 부수며 탐색하는 경로와 벽을 부수지 않고 탐색하는 경우 둘다를 확인하기 때문에 둘 다의 경우에서 최단경로를 파악할 수 있는 것이다.

그 뒤로 위 과정을 계속 반복한다.

queue의 값이 모두 빠지고 현재 좌표가 (N,M)이 되면 현재까지 구한 경로길이를 반환해준다!

 

[코드]

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

const int MAX_VALUE = 1001;
int direction[4][2] = { {0,1}, {1,0},{0,-1},{-1,0} };//이동 방향키: 오른쪽, 아래, 왼쪽, 위

class Point {
public:
	int x;
	int y;
	int breakCount;//벽을 부순 횟수. 0 or 1로 표현
	int count;//이동 횟수. 나중에 출력해줘야 함.
	Point(int x, int y, int breakCount, int count) {
		this->x = x;
		this->y = y;
		this->breakCount = breakCount;
		this->count = count;
	}
};

int MoveByBFS(int N, int M, int map[MAX_VALUE][MAX_VALUE]);//BFS를 통한 최단거리 찾기 수행

int main() {
	int N, M;
	cin >> N >> M;
	int map[MAX_VALUE][MAX_VALUE] = { 0, };
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf_s("%1d", &map[i][j]);
		}
	}
	cout << MoveByBFS(N, M, map);
	return 0;
}


int MoveByBFS(int N, int M, int map[MAX_VALUE][MAX_VALUE]) {
	queue<Point> q;
	bool visited[MAX_VALUE][MAX_VALUE][2] = { false, }; 

	q.push(Point(0,0,0,1));
	visited[0][0][0] = true;//벽을 부순 횟수가 0이면서 해당 좌표에 방문했음을 나타냄
	visited[0][0][1] = true;//벽을 부순 횟수가 1이면서 해당 좌표에 방문했음을 나타냄

	while (!q.empty()) {
		Point currentPoint = q.front();
		q.pop();

		if (currentPoint.x == N - 1 && currentPoint.y == M - 1) {
			return currentPoint.count;
		}
		for (int i = 0; i < 4; i++) {
			int nx = currentPoint.x + direction[i][0];
			int ny = currentPoint.y + direction[i][1];
			if (nx < N && nx >= 0 && ny < M && ny >= 0) {
				if (!visited[nx][ny][0]) {//벽 부순 횟수가 0이면서 해당 좌표에 방문한 적이 없는 경우
					if (map[nx][ny] == 0 && currentPoint.breakCount == 0) {//해당 좌표에 벽이 없고 이전까지 벽 부순 횟수도 0일 경우만 push
						visited[nx][ny][0] = true;
						q.push(Point(nx, ny, 0, currentPoint.count + 1));
					}
				}
				if (!visited[nx][ny][1]) {//벽 부순 횟수가 1이면서 해당 좌표에 방문한 적이 없는 경우
					if ((map[nx][ny] == 1 && currentPoint.breakCount == 0)//해당 좌표에 벽이 있고 벽 부순 횟수가 0인 경우
							|| (map[nx][ny] == 0 && currentPoint.breakCount == 1)) {//or 해당 좌표에 벽이 없고 벽 부순 횟수가 1인 경우
						visited[nx][ny][1] = true;
						q.push(Point(nx, ny, 1, currentPoint.count + 1));
					}
				}
			}
		}
	}
	return -1;
}