백준 2206번: 벽 부수고 이동하기 문제풀이 및 반례 모음

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

2206번: 벽 부수고 이동하기

1.문제설명

6 4
0100
1110
1000
0000
0111
0000

0은 이동할 수 있는 곳이고 1은 벽이다.

벽을 한번 부술 수 있을 때 (1,1)에서 (N,M) 까지 이동하는 최단 거리를 구해야한다.

 

 

 

 

 

2.접근방법[알고리즘]

맨 처음에는 없앨 벽을 선택하고, 그에 따른 최단 거리를 구해줬다.

하지만 이러면 계산량이 많아져서 시간초과가 된다.

 

2206 백준 FAQ

https://www.acmicpc.net/board/view/27386

글 읽기 - ★☆★☆★ [필독] 벽 부수고 이동하기 FAQ ★☆★☆★

백준 게시판에 좋은 글이 있어서 첨부합니다.

 

요약하자면 벽을 부수기 전과 부순 후를 나누어서 생각해야 합니다.

이동하면서 현재 좌표는 벽을 부술 수 있는 지 없는지 상태를 저장해야합니다.

또 벽을 안 부수면서 이동할 때의 방문 기록을 체크해주는 배열과

벽을 부순 후 방문 기록을 체크해주는 배열을 따로 분리해 생각해야 합니다.

 

6 4
0100
1110
1000
0000
0111
0000

위 예제에 대해서 벽을 뚫기 전과 벽을 뚫은 이후를 따로 체크해주는 배열에 거리를 저장했습니다.

 

int vis[1003][1003][2];
//vis[x][y][1 = 벽 뚫을 기회 1번 있음] , vis[x][y][0 = 벽 뚫을 기회 x]

위와 같은 방문기록을 체크해주는 vis 배열을 3차원으로 만들어

vis[x][y][1 == 벽을 뚫을 기회가 1번 있는 상태]

vis[x][y][0 == 벽을 뚫을 기회가 없는 상태, 이미 벽을 한번 뚫은 상태]

 

이렇게 저장해주어 BFS를 돌면서

벽을 뚫기 전까지는 vis[x][y][1]에 방문기록을 저장하다가

벽을 뚫는 일이 발생하면 그 이후부터는 vis[x][y][0]에 방문 기록을 저장해줍니다.

 

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m;
string arr[1003];
int vis[1003][1003][2];
//vis[x][y][1 = 벽 뚫을 기회 1번 있음] , vis[x][y][0 = 벽 뚫을 기회 x] 
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

//void print() {
//	for (int k = 1; k >= 0; k--) {
//		if (k == 1) {
//			cout << "벽 뚫기 전 \n";
//		}
//		else {
//			cout << "벽 뚫은 후 \n";
//		}
//		for (int i = 0; i < n; i++) {
//			for (int j = 0; j < m; j++) {
//				cout << vis[i][j][k] << ' ';
//			}
//			cout << '\n';
//		}
//	}
//	cout << "\n";
//}

struct Edge {
	int x, y, op;
	Edge(int a, int b, int c) {
		x = a;
		y = b;
		op = c;
	}
};


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	queue<Edge> Q;
	Q.push(Edge(0,0,1));
	// 0에 좌표 방문 저장, 1에 벽 부쉇는지 저장 
	vis[0][0][1] = 1;
	vis[0][0][0] = 0;

	while (!Q.empty()) {
		int x = Q.front().x;
		int y = Q.front().y;
		int op = Q.front().op;
		Q.pop();

		//print();

		if (x == n - 1 && y == m - 1) {
			//도착 점 방문 시 이동하는데 걸린 거리 출력 
			if (vis[n - 1][m - 1][0] == 0)
				cout << vis[n - 1][m - 1][1];
			else
				cout << vis[n - 1][m - 1][0];
			return 0;
		}

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (op == 1) {
				//벽 부순적 없음 1도 방문 가능
				if (vis[nx][ny][1] == 0) {
					// 0 방문 할 떄 
					if (arr[nx][ny] == '0') {
						Q.push(Edge(nx, ny, 1));
						vis[nx][ny][1] = vis[x][y][1] + 1;
					}
					else { // 1 방문할 떄 
						Q.push(Edge(nx, ny, 0));
						vis[nx][ny][0] = vis[x][y][1] + 1;
					}
				}
			}
			else {
				//벽 부순적 있음 
				//
				if (vis[nx][ny][0] == 0 && vis[nx][ny][1]==0) {
					if (arr[nx][ny] == '0') {
						Q.push(Edge(nx, ny, 0));
						vis[nx][ny][0] = vis[x][y][0] + 1;
					}
				}

			}
		}
	}

	cout << -1;
	return 0;
}

백준 2206 메모리 및 시간

 

 

4. 2206 반례 

백준 2206번 벽부수기 반례, 테스트케이스 모음입니다.

1.

5 8
01000000
01010000
01010000
01010011
00010010

 

2.

8 8
01000100
01010100
01010100
01010100
01010100
01010100
01010100
00010100

3.

3 3
011
111
110

4.

 

6 7
0000000
0111111
0100010
0101010
0101010
0001010