BOJ 2206 - 벽 부수고 이동하기

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

2206번: 벽 부수고 이동하기

 

 

1차 시도

부수는 경우와 부수지 않는 경우 총 두가지의 경로가 존재한다.

따라서, 이를 해결하기 위해 부수는 경우를 이차원 배열을 이용하여 저장하려고 시도하였다.

broken[][]

map[][]

chk[][]

 

그러나 이에 대한 문제가 존재한다.

만약 벽을 하나도 부수지 않는 경우에 이를 이용하면, 도달하지 못한다는 결과가 도출된다.

이런 문제가 발생하는 이유는 벽을 부순 지점만 저장하고 벽을 부수고 진행한 경로 자체는 저장을 하지 않기 때문이다.

 

따라서, 이를 해결하기 위해 부순 경우도 함께 저장하는 queue를 만들면 된다고 생각했다.

(파괴 유무, x, y)를 한쌍으로

이를 이용하면, 파괴 유무에 따라 이동할 조건을 추가해주기 수월하다.

 

다른 블로그를 참고하여 tuple이라는 STL을 이용한다고 하여 이를 사용하였다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>

#define MAX 1001

using namespace std;

int n, m;
int map[MAX][MAX];
int res[2][MAX][MAX];
bool chk[2][MAX][MAX];
queue<tuple<int, int, int>> q;
int xPos[4] = { -1,1,0,0 };
int yPos[4] = { 0,0,-1, 1 };

void bfs(int x, int y) {
	q.push(make_tuple(0, x, y));
	chk[0][x][y] = true;
	res[0][x][y] = 1;

	while (!q.empty()) {
		tuple<int, int,int> curr = q.front();
		q.pop();
		
		int currX = get<1>(curr);
		int currY = get<2>(curr);

		for (int i = 0; i < 4; i++) {
			int broken = get<0>(curr);
			int movedX = currX + xPos[i];
			int movedY = currY + yPos[i];

			if (movedX < 1 || movedY < 1 || movedX > n || movedY > m) continue;

			// 벽을 이미 부쉈으면 안부수고 패스
			if (broken && !chk[broken][movedX][movedY]) {
				// 벽이 아니면 그대로 이동
				if (map[movedX][movedY] != 1) {
					chk[broken][movedX][movedY] = true;
					res[broken][movedX][movedY] = res[broken][currX][currY] + 1;
					q.push(make_tuple(broken, movedX, movedY));
				}
			}
			// 벽을 안부쉈으면 그대로 패스
			else if (!broken && !chk[broken][movedX][movedY]) {
				// 1이면 부수고 이동
				if (map[movedX][movedY] == 1) {
					chk[1][movedX][movedY] = true;
					res[1][movedX][movedY] = res[0][currX][currY] + 1;
					q.push(make_tuple(1, movedX, movedY));
				}
				// 0이면 그냥 이동
				else {
					chk[0][movedX][movedY] = true;
					res[0][movedX][movedY] = res[0][currX][currY] + 1;
					q.push(make_tuple(0, movedX, movedY));
				}
			}
			
		}
	}
}

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

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		string str;
		cin >> str;
		for (int j = 1; j <= m; j++) {
			map[i][j] = (int)(str[j-1]-'0');
		}
	}
	
	bfs(1, 1);

	if (res[1][n][m] == 0 && res[0][n][m] == 0)
		cout << -1;
	else {
		if (res[0][n][m] == 0)	cout << res[1][n][m];
		else if (res[1][n][m] == 0) cout << res[0][n][m];
		else cout << min(res[0][n][m], res[1][n][m]);
	}
		
}