[BAEKJOON] 2206번:벽 부수고 이동하기*

문 제

 

소 스  코 드

#include <iostream>
#include <queue>
struct Log {
	int x, y, w;
};

int dp[1001][1001][2];
int dx[4]	{ -1, 0, 1, 0 };
int dy[4]	{ 0, 1, 0, -1 };


int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	int N, M;

	std::cin >> N >> M;

	char** walls{ new char*[N] };
	
	for (int i = 0; i < N; ++i) walls[i] = new char[M + 1];
	for (int i = 0; i < N; ++i) std::cin >> walls[i];
	
	std::queue<Log> bfs;
	bfs.push({ 0, 0, 0 });
	dp[0][0][0] = 1;

	int lev{ -1 };
	while (!bfs.empty()) {
		Log temp{ bfs.front() };
		bfs.pop();

		if ((N - 1 == temp.x) && (M - 1 == temp.y)) {
			lev = dp[temp.x][temp.y][temp.w];
			break;
		}

		for (int i = 0; i < 4; ++i) {
			int x{ temp.x + dx[i] };
			int y{ temp.y + dy[i] };

			if (x < 0 || x > N - 1 || y < 0 || y > M - 1) continue;
			if (dp[x][y][temp.w]) continue;

			if ('0' == walls[x][y]) {
				dp[x][y][temp.w] = dp[temp.x][temp.y][temp.w] + 1;
				bfs.push({ x, y, temp.w });
			}
			if ('1' == walls[x][y] && (0 == temp.w)) {
				dp[x][y][1] = dp[temp.x][temp.y][temp.w] + 1;
				bfs.push({ x, y, 1 });
			}
		}
	}

	std::cout << lev << '\n';

	for (int i = 0; i < N; ++i) delete[] walls[i];
	delete[] walls;

	return 0;
}

 

풀 이

 

• 최단 거리를 찾는 문제

• 잘못된 코드 (시간 초과)

#include <iostream>
#include <queue>
struct Log {
	int x, y;
	int level;
	bool tf;
};

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	int N, M;

	std::cin >> N >> M;

	char** walls{ new char*[N] };
	
	for (int i = 0; i < N; ++i) walls[i] = new char[M + 1];
	for (int i = 0; i < N; ++i) std::cin >> walls[i];
	
	std::queue<Log> bfs;
	bfs.push({ 0, 0, 1, false });
	walls[0][0] = '2';

	int lev;
	while (!bfs.empty()) {
		Log temp{ bfs.front() };
		bfs.pop();

		char loadState{ '2' };
		if (temp.tf) loadState = '3';

		if ((N - 1 == temp.x) && (M - 1 == temp.y)) {
			lev = temp.level;
			break;
		}

		if ((temp.x > 0) && ('2' != walls[temp.x - 1][temp.y])) {
			if (('1' == walls[temp.x - 1][temp.y]) && !temp.tf) {
				bfs.push({ temp.x - 1, temp.y, temp.level + 1, true });
			}
			else if ('1' != walls[temp.x - 1][temp.y]) {
				walls[temp.x - 1][temp.y] = loadState;
				bfs.push({ temp.x - 1, temp.y, temp.level + 1, temp.tf });
			}
		}

		if ((temp.x < N - 1) && ('2' != walls[temp.x + 1][temp.y])) {
			if (('1' == walls[temp.x + 1][temp.y]) && !temp.tf) {
				bfs.push({ temp.x + 1, temp.y, temp.level + 1, true });
			}
			else if ('1' != walls[temp.x + 1][temp.y]) {
				walls[temp.x + 1][temp.y] = loadState;
				bfs.push({ temp.x + 1, temp.y, temp.level + 1, temp.tf });
			}
		}


		if ((temp.y > 0) && ('2' != walls[temp.x][temp.y - 1])) {
			if (('1' == walls[temp.x][temp.y - 1]) && !temp.tf) {
				bfs.push({ temp.x, temp.y - 1, temp.level + 1, true });
			}
			else if ('1' != walls[temp.x][temp.y - 1]) {
				walls[temp.x][temp.y - 1] = loadState;
				bfs.push({ temp.x, temp.y - 1, temp.level + 1, temp.tf });
			}
		}

		if ((temp.y < M - 1) && ('2' != walls[temp.x][temp.y + 1])) {
			if (('1' == walls[temp.x][temp.y + 1]) && !temp.tf) {
				bfs.push({ temp.x, temp.y + 1, temp.level + 1, true });
			}
			else if ('1' != walls[temp.x][temp.y + 1]) {
				walls[temp.x][temp.y + 1] = loadState;
				bfs.push({ temp.x, temp.y + 1, temp.level + 1, temp.tf });
			}
		}

	}

	if (walls[N - 1][M - 1] == '0' || walls[N - 1][M - 1] == '1')	std::cout << "-1 \n";
	else															std::cout << lev << '\n';
	

	for (int i = 0; i < N; ++i) delete[] walls[i];
	delete[] walls;

	return 0;
}

- [0] 벽을 부수지 않고 (N, M)에 도착하는 2차원 배열 경로.

- [1] 벽을 부수고 (N, M)에 도착하는 2차우너 배열 경로.

 

위의 두가지로 나누는 이유는, 

한 번 벽을 부수고 지나가는 최단 경로를 찾을 경우. 

벽을 부수지 않고 지나가다 벽을 부수고 지나가는 최단 경로의 경우.

 

후자에 있는 경우가 최단 거리 일 경우, 이미 먼저 선점한 전자의 경우로 인하여 재대로된 탐색을 할 수 없습니다.

 

반례 예시, - 출처 링크

5 10
0000011000
1101011010
0000000010
1111111110
1111000000

 

위의 경우에 

2000011222 
2101011212 
2222222212 
1111111112 
1111000002

 

2222211000 
1101211010 
0000200010 
1111211110 
1111222222

 

이런식의 결과가 나올 수 있는데, 하나의 경로로만 관리한다면

최단거리를 찾을 수 없습니다.

 

참고 링크

 

출 력 값

 

 

문 제  출 처

문제 링크 : www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기