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

3차원 벡터를 사용하여 해당 위치에 벽을 부수고 왔는지, 벽을 부수지 않고 왔는지 여부를 확인해야 한다. 그 후 BFS를 사용하여 목적지까지 갈 수 있는지 확인한다.

 

 

board는 맵을 뜻하고 dis는 해당 위치까지의 거리를 뜻한다. 위에서 말했듯이 벽의 파괴 여부를 체크하기 위해 3차원 벡터로 선언했고 세번째 index가 0일 경우 부수지 않고 온 경우, 1인 경우 벽을 부수고 온 경우를 뜻한다.

 

 

그래서 큐의 자료형도 tuple을 사용하여 해당 위치에 벽의 파괴 여부를 표시했다. 만약 q에 { 1, 2, 1 }이 있으면 (1, 2)에 벽을 부수고 도달했다는 뜻이다.

 

 

이제 BFS를 적용할텐데 현재 위치가

1) 벽을 부수고 온 경우

 1-1) 다음 위치가 벽이 아닌 경우

     - 다음 위치가 벽을 부수고 방문한 적이 있는 경우 -> 거리 비교

     - 다음 위치가 벽을 부수고 방문한 적이 없는 경우

 1-2) 다음 위치가 벽인 경우 (못 가므로 pass)

2) 벽을 부수지 않고 온 경우

 2-1) 다음 위치가 벽이 아닌 경우

     - 다음 위치가 벽을 부수지 않고 방문한 적이 있는 경우 -> 거리 비교

     - 다음 위치가 벽을 부수지 않고 방문한 적이 없는 경우

 2-2) 다음 위치가 벽인 경우

     - 다음 위치가 벽을 부수고 방문한 적이 있는 경우 -> 거리 비교

     - 다음 위치가 벽을 부수고 방문한 적이 없는 경우

이렇게 경우의 수가 나뉘어진다.

q에서 뽑은 cur의 세 번째 인자값이 1인 경우 벽을 부수고 온 경우다. 다음 위치에 방문한 경우가 없는 경우 현재 위치까지의 거리 + 1을 넣어주고 방문한 경우가 있으면 비교를 해서 더 작은 값을 넣어준다.

 

 

벽을 부수지 않고 온 경우다. 위와 달리 벽을 부수지 않고 온 경우는 벽을 부수고 갈 수 있으므로 다음 위치가 벽인 경우까지 확인해야 한다.

 

 

목적지에 도달을 하지 못했으면 dis[N-1][M-1][0]과 dis[N-1][M-1][1] 둘 다 0일 것이고 하나만 도달했을 경우 도달한 경우를 출력하고 둘 다 도달했을 경우 더 작은 값을 출력한다.

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,-1,0,1 };

int N, M;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;

	if (N == 1 and M == 1) {
		cout << 1;
		return 0;
	}

	vector<vector<int>> board(1001, vector<int>(1001, 0)); // 맵
	// 출발지 ~ 해당 위치까지의 거리
	// 3차원 배열의 0번째는 벽을 뚫지 않고 온 경우의 거리를 뜻하고
	// 1번째는 벽을 뚫고 온 경우의 거리를 뜻한다.
	// dis[5][3][1] = 10 인 경우 5,3까지 벽을 한 번 뚫고 10칸 걸린다는 뜻
	vector<vector<vector<int>>> dis(1001, vector<vector<int>>(1001, vector<int>(2, 0))); 

	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;

		for (int j = 0; j < str.length(); j++) {
			board[i][j] = str[j] - '0';
		}
	}

	// 튜플은 { 행, 열, 현재 위치까지 벽을 뚫고 왔는지에 대한 여부 } 을 뜻한다.
	// 세번째 값이 0인 경우는 벽을 뚫고 오지 않음, 1인 경우 벽을 뚫고 왔다는 뜻
	queue<tuple<int,int,int>> q;
	q.push({ 0,0,0 });

	while (!q.empty()) {
		auto cur = q.front();
		q.pop();

		for (int k = 0; k < 4; k++) {
			int xpos = get<0>(cur) + dx[k];
			int ypos = get<1>(cur) + dy[k];

			if (xpos == 0 and ypos == 0)
				continue;

			if (xpos < 0 or xpos >= N or ypos < 0 or ypos >= M)
				continue;

			if (get<2>(cur) > 0) {	// 벽을 부수고 온 경우
				if (board[xpos][ypos] < 1) { // 다음이 벽이 아닌 경우
					if (dis[xpos][ypos][1] == 0) {	// 다음 위치가 벽을 부수고 방문한 경우가 없을 때
						dis[xpos][ypos][1] = dis[get<0>(cur)][get<1>(cur)][1] + 1;
						q.push({ xpos,ypos,1 });
					}
					else { // 다음 위치가 벽을 부수고 방문한 경우가 있을 때
						// 거리를 비교한다.
						if (dis[xpos][ypos][1] > dis[get<0>(cur)][get<1>(cur)][1] + 1) {
							dis[xpos][ypos][1] = dis[get<0>(cur)][get<1>(cur)][1] + 1;
							q.push({ xpos,ypos,1 });
						}
					}
				}
			}
			else {	// 벽을 안부수고 온 경우
				if (board[xpos][ypos] < 1) { // 다음이 벽이 아닌 경우
					if (dis[xpos][ypos][0] == 0) {	// 다음 위치가 벽을 안부수고 방문한 경우가 없을 때
						dis[xpos][ypos][0] = dis[get<0>(cur)][get<1>(cur)][0] + 1;
						q.push({ xpos,ypos,0 });
					}
					else { // 다음 위치가 벽을 안부수고 방문한 경우가 있을 때
						// 거리를 비교한다.
						if (dis[xpos][ypos][0] > dis[get<0>(cur)][get<1>(cur)][0] + 1) {
							dis[xpos][ypos][0] = dis[get<0>(cur)][get<1>(cur)][0] + 1;
							q.push({ xpos,ypos,0});
						}
					}
				}
				else { // 다음 위치가 벽인 경우
					if (dis[xpos][ypos][1] > 0) { // 다음 위치가 벽을 부수고 방문한 경우가 있을 때
						// 거리를 비교한다.
						if (dis[xpos][ypos][1] > dis[get<0>(cur)][get<1>(cur)][0] + 1) {
							dis[xpos][ypos][1] = dis[get<0>(cur)][get<1>(cur)][0] + 1;
							q.push({ xpos,ypos,1 });
						}
					}
					else { // 다음 위치가 벽을 부수고 방문한 경우가 없을 때
						dis[xpos][ypos][1] = dis[get<0>(cur)][get<1>(cur)][0] + 1;
						q.push({ xpos,ypos, 1 });
					}
				}
			}
		}
	}

	// 목적지에 도착을 못한 경우
	if (max(dis[N - 1][M - 1][0], dis[N - 1][M - 1][1]) == 0)
		cout << -1;
	else { // 목적지에 벽을 부수고 오거나, 벽을 부수지 않고 도착한 경우
		if (dis[N - 1][M - 1][0] > 0 and dis[N - 1][M - 1][1] > 0)
			// 벽을 부수고 온 경우와 벽을 부수고 오지 않은 경우 둘 다 있을 때
			// 둘 중 작은 것을 출력해야 한다.
			cout << min(dis[N - 1][M - 1][0], dis[N - 1][M - 1][1]) + 1;
		else
			// 벽을 부수고 온 경우와 벽을 부수고 오지 않은 경우 중 하나만 있을 때
			// 벽을 부수고 온 경우는 0이므로 둘 중 큰 값을 출력해야 한다.
			cout << max(dis[N - 1][M - 1][0], dis[N - 1][M - 1][1]) + 1;
	}

	return 0;
}