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

프로그래밍/PS

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

유태정 2021. 2. 23. 13:37

풀이 과정

오답: 시간초과(2%)

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int N, M;
	cin >> N >> M;

	vector<pair<int, int>> walls(1, make_pair(0, 0));
	vector<vector<int>> maze(N, vector<int>(M));
	FOR(r, N) {
		string line;
		cin >> line;
		FOR(c, M) {
			maze[r][c] = line[c] - '0';
			if (line[c] - '0' == 1)
				walls.push_back(make_pair(r, c));
		}
	}

	constexpr int adjs[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
	int min_length = INF;
	for (auto& wall : walls) {
		auto& [_r, _c] = wall;
		int origin = maze[_r][_c];
		maze[_r][_c] = 0;

		vector<vector<bool>> mark(N, vector<bool>(M, false));
		//			r  , c  , length
		queue<tuple<int, int, int>> BFS;
		BFS.push(make_tuple(0, 0, 1));
		mark[0][0] = true;

		while (!BFS.empty()) {
			auto [r, c, l] = BFS.front();
			BFS.pop();

			if (r == N - 1 && c == M - 1) {
				min_length = min(min_length, l);
				break;
			}

			for (auto& adj : adjs) {
				auto& [dr, dc] = adj;
				if (r + dr < 0 || r + dr >= N) continue;
				if (c + dc < 0 || c + dc >= M) continue;
				if (maze[r + dr][c + dc] == 1) continue;
				if (mark[r + dr][c + dc]) continue;

				BFS.push(make_tuple(r + dr, c + dc, l + 1));
				mark[r + dr][c + dc] = true;
			}
		}

		maze[_r][_c] = origin;
	}

	min_length < INF ? cout << min_length << EL : cout << -1 << EL;

	return 0;
}

위 코드에서는 M * N의 각 블록을 한 번씩 0으로 만든 위 너비우선 탐색을 진행한다.

시간복잡도는 \(log(N^{2}M^{2})\)이므로 최대 1,000,000,000,000번의 연산이 필요하다.

따라서 제한시간 내에 모든 연산을 마칠 수 없다.

오답: 틀렸습니다(11%)

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int N, M;
	cin >> N >> M;

	vector<vector<int>> maze(N, vector<int>(M));
	FOR(r, N) {
		string line;
		cin >> line;
		FOR(c, M)
			maze[r][c] = line[c] - '0';
	}

	constexpr int adjs[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
	int min_length = INF;

	vector<vector<bool>> mark(N, vector<bool>(M, false));
	queue<tuple<int, int, int, bool>> BFS;
	BFS.push(make_tuple(0, 0, 1, true));
	mark[0][0] = true;

	while (!BFS.empty()) {
		auto [r, c, l, available] = BFS.front();
		BFS.pop();

		if (r == N - 1 && c == M - 1) {
			min_length = min(min_length, l);
			break;
		}

		for (auto& adj : adjs) {
			auto& [dr, dc] = adj;
			if (r + dr < 0 || r + dr >= N) continue;
			if (c + dc < 0 || c + dc >= M) continue;
			if (mark[r + dr][c + dc]) continue;
			if (maze[r + dr][c + dc] == 1) {
				if (available) {
					BFS.push(make_tuple(r + dr, c + dc, l + 1, false));
					mark[r + dr][c + dc] = true;
				}
				continue;
			}
			BFS.push(make_tuple(r + dr, c + dc, l + 1, available));
			mark[r + dr][c + dc] = true;
		}
	}

	min_length < INF ? cout << min_length << EL : cout << -1 << EL;

	return 0;
}

타 블로그의 풀이를 참고했다.

Queue의 네 번째 위치에 "벽 부수기" 능력을 쓸 수 있는지 여부를 담았다.

실행 속도는 빨라졌으나, "벽 부수기" 능력을 쓸 때마다의 분기를 제대로 처리하지 못 했다.

방문확인을 나타내는 mark 변수를 각 "벽 부수기" 시점마다 복제하여 충분히 탐색할 수 있도록 해줘야 한다.

오답: 틀렸습니다(11%)

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int N, M;
	cin >> N >> M;

	vector<vector<int>> maze(N, vector<int>(M));
	FOR(r, N) {
		string line;
		cin >> line;
		FOR(c, M)
			maze[r][c] = line[c] - '0';
	}

	constexpr int adjs[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
	int min_length = INF;

	vector<vector<vector<bool>>> mark(1, vector<vector<bool>>(N, vector<bool>(M, false)));
	queue<tuple<int, int, int, int>> BFS;
	BFS.push(make_tuple(0, 0, 1, 0));
	mark[0][0][0] = true;

	while (!BFS.empty()) {
		auto [r, c, l, available] = BFS.front();
		BFS.pop();

		if (r == N - 1 && c == M - 1) {
			min_length = min(min_length, l);
			break;
		}

		for (auto& adj : adjs) {
			auto& [dr, dc] = adj;
			if (r + dr < 0 || r + dr >= N) continue;
			if (c + dc < 0 || c + dc >= M) continue;
			if (mark[available][r + dr][c + dc]) continue;
			if (maze[r + dr][c + dc] == 1) {
				if (available == 0) {
					mark.push_back(mark.back());
					available = mark.size() - 1;
					BFS.push(make_tuple(r + dr, c + dc, l + 1, available));
					mark[available][r + dr][c + dc] = true;
				}
				continue;
			}
			BFS.push(make_tuple(r + dr, c + dc, l + 1, available));
			mark[available][r + dr][c + dc] = true;
		}
	}

	min_length < INF ? cout << min_length << EL : cout << -1 << EL;

	return 0;
}

능력을 안 썼을 때, Queue의 네 번째 요소인 available의 값은 0이다.

능력을 썼을 때, mark는 마지막 요소를 복제하고 available의 값은 mark의 크기 - 1로 바뀐다.

평행세계가 열린다고 생각하면 된다.

방문 확인은 available의 값에 따라 달라진다.

위에서 available 값을 복사해서 갱신했어야 했지만, 기존 변수를 이용하여 이후 인접 칸을 방문할 때 영향을 끼쳤다.

그래서 오답이 나왔다.

오답: 메모리 초과(11%)

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int N, M;
	cin >> N >> M;

	vector<vector<int>> maze(N, vector<int>(M));
	FOR(r, N) {
		string line;
		cin >> line;
		FOR(c, M)
			maze[r][c] = line[c] - '0';
	}

	constexpr int adjs[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
	int min_length = INF;

	vector<vector<vector<bool>>> mark(1, vector<vector<bool>>(N, vector<bool>(M, false)));
	queue<tuple<int, int, int, int>> BFS;
	BFS.push(make_tuple(0, 0, 1, 0));
	mark[0][0][0] = true;

	while (!BFS.empty()) {
		auto [r, c, l, available] = BFS.front();
		BFS.pop();

		if (r == N - 1 && c == M - 1) {
			min_length = min(min_length, l);
			break;
		}

		for (auto& adj : adjs) {
			auto& [dr, dc] = adj;
			if (r + dr < 0 || r + dr >= N) continue;
			if (c + dc < 0 || c + dc >= M) continue;
			if (mark[available][r + dr][c + dc]) continue;
			if (maze[r + dr][c + dc] == 1) {
				if (available == 0) {
					mark.push_back(mark.back());
					int n_available = mark.size() - 1;
					BFS.push(make_tuple(r + dr, c + dc, l + 1, n_available));
					mark[n_available][r + dr][c + dc] = true;
				}
				continue;
			}
			BFS.push(make_tuple(r + dr, c + dc, l + 1, available));
			mark[available][r + dr][c + dc] = true;
		}
	}

	min_length < INF ? cout << min_length << EL : cout << -1 << EL;

	return 0;
}

평행세계가 열릴 때마다 방문확인 mark를 하나씩 복제하니, 결국 벽의 개수만큼 복제가 된다.

최대 크기가 \(MN(MN-2) ≤ 999,998,000,000 byte\)이다.

정답: 맞았습니다!!

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int N, M;
	cin >> N >> M;

	vector<vector<int>> maze(N, vector<int>(M));
	FOR(r, N) {
		string line;
		cin >> line;
		FOR(c, M)
			maze[r][c] = line[c] - '0';
	}

	constexpr int adjs[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
	int min_length = INF;

	vector<vector<bool>> mark[2];
	mark[0] = vector<vector<bool>>(N, vector<bool>(M, false));
	mark[1] = vector<vector<bool>>(N, vector<bool>(M, false));

	queue<tuple<int, int, int, bool>> BFS;
	BFS.push(make_tuple(0, 0, 1, true));
	mark[0][0][0] = true;

	while (!BFS.empty()) {
		auto [r, c, l, available] = BFS.front();
		BFS.pop();

		if (r == N - 1 && c == M - 1) {
			min_length = min(min_length, l);
			break;
		}

		for (auto& adj : adjs) {
			auto& [dr, dc] = adj;
			if (r + dr < 0 || r + dr >= N) continue;
			if (c + dc < 0 || c + dc >= M) continue;
			if (mark[available][r + dr][c + dc]) continue;
			if (maze[r + dr][c + dc] == 1) {
				if (available) {
					BFS.push(make_tuple(r + dr, c + dc, l + 1, false));
					mark[false][r + dr][c + dc] = true;
				}
				continue;
			}
			BFS.push(make_tuple(r + dr, c + dc, l + 1, available));
			mark[available][r + dr][c + dc] = true;
		}
	}

	min_length < INF ? cout << min_length << EL : cout << -1 << EL;

	return 0;
}

벽을 부술 때마다 새로운 mark를 복제할 필요가 없다.

1번 블럭을 부수는 경우와 2번 블럭을 부수는 경우에서 각 독립적인 경로인데도 불구하고,

서로의 각 경우에서 지나갔던 블록을 지나갈 수 없음이 최단거리에 영향을 끼치지 않는다.

왜냐하면 이미 블록을 부순 상태이면 어자피 0으로 표시된 블록만 갈 수 있을 것이고,

그렇지 않다면 1로 표시된 블록 중 방문하지 않았던 블록을 부수면서 진행할 수 있기 때문이다.