벽 부수고 이동하기 (feat. 백준, 2206번)

벽 부수고 이동하기
https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
int N, M, arr[1000][1000], tmp[1000][1000][2], dx[4], dy[4];
vector<int> ans;
void bfs() {
	register int x, y, w;
	queue<tuple<int, int, int>> q;
	tmp[0][0][0] = 1;
	q.push(make_tuple(0, 0, 0));
	while (!q.empty()) {
		auto p = q.front(); q.pop();
		x = std::get<0>(p), y = std::get<1>(p), w = std::get<2>(p);
		for (register int d = 0, nx, ny; d < 4; ++d) {
			nx = x + dx[d], ny = y + dy[d];
			if (0 <= nx && nx < N && 0 <= ny && ny < M)
				if (arr[nx][ny] == 0 && !tmp[nx][ny][w])
					tmp[nx][ny][w] = tmp[x][y][w] + 1, q.push(make_tuple(nx, ny, w));
				else if(arr[nx][ny] == 1 && w == 0 && !tmp[nx][ny][w + 1])
					tmp[nx][ny][w + 1] = tmp[x][y][w] + 1, q.push(make_tuple(nx, ny, w + 1));
		}
	}
	if (tmp[N - 1][M - 1][0])
		ans.push_back(tmp[N - 1][M - 1][0]);
	if (tmp[N - 1][M - 1][1])
		ans.push_back(tmp[N - 1][M - 1][1]);
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
	dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
	memset(tmp, 0, sizeof(tmp));
	cin >> N >> M;
	char tmp;
	for (register int i = 0, j; i < N; ++i)
		for (j = 0; j < M; ++j)
			cin >> tmp, arr[i][j] = tmp - '0';
	bfs();
	if (ans.empty())
		cout << -1;
	else
		cout << *min_element(ans.begin(), ans.end());
	return 0;
}
// *&)*@*

1. 모든 벽에 대해서 BFS를 진행하는 방식은 최대 N * M (1000 * 1000) 번을 반복하게 되므로 시간 초과가 나오게 됩니다.
2. 좌우상하가 벽인 경우와 벽이 아닌 경우에 대해서 한번에 계산해서 값을 도출하는 것이 포인트입니다.