백준 C++ 알고리즘 2206: 벽 부수고 이동하기

 

여러 시도 끝에 풀어낸 문제다.

 

기본적으로 BFS로 풀어야 하며, 벽을 뚫을 수 있는 기회가 한 번 있다고 알려준다.

 

처음에는 벽이 있는 횟수 만큼 BFS를 반복했다. BFS를 반복하면서 배열도 초기화 해주며 n,m 자리의 최소값을 갱신했다.

 

그렇지만 이 방법은 시간 복잡도가 매우 높아지므로 시간초과가 날 수 밖에 없다.

 

그래서 벽을 뚫었는지의 유무를 큐에 추가했다.

 

큐에 벽을 뚫었는지의 유무를 추가하여 BFS를 한 번 돌려 답을 구할 수 있도록 문제를 재정의 한 것이다.

 

물론 시행착오가 있었다. 메모리초과가 발생하는 것이다.

 

그래서 생각해낸 것이, 벽을 뚫은 큐의 원소들에게는 다른 저장소를 부여하는 것이다.

 

벽을 뚫지 않은 것들의 가중치(거리의 합)은 원래 장소에 저장하고, 벽을 뚫은 것들을 모아 따로 계산해주었다.

 

또한, 벽을 뚫지 않은 것들의 가중치를 갱신할 때 벽을 뚫은 것들의 가중치 또한 같이 갱신해 주어 메모리를 줄이려 했다.

 

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

int list[1001][1001] = {};
std::vector<std::vector<int>> dp(1001, std::vector<int>(1001,INT_MAX));
std::vector<std::vector<int>> dp2(1001, std::vector<int>(1001, INT_MAX));

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

	int n, m;
	std::cin >> n >> m;
	std::string tmp;

	for (int i{ 1 }; i <= n; i++) {
		std::cin >> tmp;
		for (int j{ 0 }; j < m; j++) {
			list[i][j+1] = tmp[j] - '0';
		}
	}
	
	int t[] = { 1, 0, -1, 0 };
	int y[] = { 0, 1, 0, -1 };

	dp[1][1] = 1;
	
	std::queue<std::tuple<int, int, int>> q;
	q.push({ 1,1,0 });
	while (!q.empty()) {
		int a = std::get<0>(q.front());
		int b = std::get<1>(q.front());
		int c = std::get<2>(q.front());
		q.pop();

		if (c == 1) {
			for (int i{ 0 }; i < 4; i++) {
				if (a + y[i] > 0 && a + y[i] <= n && b + t[i] > 0 && b + t[i] <= m && list[a + y[i]][b + t[i]] == 0 && dp2[a + y[i]][b + t[i]] > dp2[a][b] + 1) {
					q.push({ a + y[i], b + t[i], c });
					dp2[a + y[i]][b + t[i]] = dp2[a][b] + 1;
				}
			}
		}
		else {
			for (int i{ 0 }; i < 4; i++) {
				if (a + y[i] > 0 && a + y[i] <= n && b + t[i] > 0 && b + t[i] <= m && dp[a + y[i]][b + t[i]] > dp[a][b] + 1) {
					if (list[a + y[i]][b + t[i]] == 1) {
						q.push({ a + y[i], b + t[i], 1 });
						dp2[a + y[i]][b + t[i]] = dp[a][b] + 1;
					}
					else {
						q.push({ a + y[i], b + t[i], 0 });
						dp[a + y[i]][b + t[i]] = dp[a][b] + 1;
					}

					//std::cout << a + y[i] << " " << b + t[i] << " ay, at\n";
				}
			}
		}

		////std::cout << dp[a][b] << " a, b : " << a << " " << b << "\n";
	}

	if (dp[n][m] == INT_MAX && dp2[n][m] == INT_MAX) std::cout << "-1\n";
	else std::cout << std::min(dp[n][m],dp2[n][m]) << "\n";
}