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

 

1) 문제설명

백준 Online Judge 2206번 벽 부수고 이동하기

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

2206번: 벽 부수고 이동하기

 

2) 아이디어

벽을 한 번만 부술 수 있기 때문에 처음에는 단순히 벽이 가로막고 있고 그 벽 다음이 뚫려있다면 벽을 뚫고 BFS를 순환하도록 구현하였는데 철저하게 틀린 답이었다. 먼저 벽을 뚫었을 때의 거리와 벽을 뚫지 않았을 때의 거리 중 뭐가 최소가 나오는지 알 수 없었고 벽을 먼저 뚫고 지나가면 나중에 나오는 벽을 뚫을 수없어 목표지점에 도달하지 못할 수도 있었다.

따라서 이 2가지를 생각하면서 구현을 해야 했다.

1. 벽을 뚫었을 때의 거리 VS 벽을 뚫지 않았을 때 거리

2. 처음에만 벽을 뚫는 것이 아닌 나중에도 벽을 뚫어야 한다.

이 두 가지를 해결하기 위해 3차원 배열을 사용하였다. [x좌표][y좌표][벽을 뚫었을 때/ 뚫지 않았을 때]

벽을 뚫었을 때와 뚫지 않았을 때의 저장공간이 다르기 때문에 앞의 2가지를 모두 해결할 수 있었다.

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;
int arr[1001][1001];
int visited[1001][1001][2]; // 방문표시
int range[1001][1001][2]; // 거리계산
int n, m, result;
typedef struct {
	int x, y, w;
}st;
queue<st> q;
int bfs(int x, int y, int w) { // w가 0이면 아직 벽을 부수지 않았다.
	q.push({ x, y, 0 }); // 처음 1,1,0
	arr[x][y] = 0; 
	if (m == x && n == y) {
		return 1;
	}
	while (!q.empty()) {
		x = q.front().x;
		y = q.front().y;
		w = q.front().w;

		q.pop();

		if (x == n && y == m) {
			return result = range[x][y][w] + 1;
		}
		int dx[] = { 0,0,-1,1 };
		int dy[] = { 1,-1,0,0 };

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx<1 || ny<1 || nx>n || ny>m || arr[nx][ny] == -1) { // 범위를 벗어나거나 이미 방문한 곳일경우
				continue;
			}
			else if (arr[nx][ny] == 0 && visited[nx][ny][w] == 0) { // 벽이 없고 방문하지 않은 곳일때
				visited[nx][ny][w] = 1; // 방문표시
				q.push({ nx,ny, w }); // 큐에 넣고
				range[nx][ny][w] = range[x][y][w] + 1; // 범위 + 1
			}
			else if (arr[nx][ny] == 1 && w == 0) { // 벽이 있고 벽을 아직 뚫지 않았을때 (w가 0이 아니면 벽을 더 뚫지 못한다.)
				visited[nx][ny][w+1] = 1; // 벽을 뚫었다는표시 (w가 0일때의 방문과 w가 1일때의 방문이 다르다)
				q.push({ nx,ny,w+1}); // w = w+1 : w가 1이되므로 다음에 이 조건문을 통과하지 못하여 벽을 더뚫지 못함
				range[nx][ny][w+1] = range[x][y][w] + 1; // 벽을 뚫었을때의 범위를 따로 계산한다.
			}
			
		}
		
	}
	return -1;
}
int main() {

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%1d", &arr[i][j]);
		}
	}
	cout << bfs(1, 1, 0) << endl;
	

}