c++ 2206 벽 부수고 이동하기 (백준)

#include <bits/stdc++.h>
#define Q q.front()

using namespace std;

struct A {
	A(int a, int b, int c, int d) : x(a), y(b), z(c), value(d) {}
	int x, y, z, value;
};

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int V[4] = {-1, 0, 1, 0};
	int H[4] = {0, 1, 0, -1};
	int n, m, min = 1e9;
	cin >> n >> m;
	if(n==1 && m==1) {
        cout << 1;
        return 0;
    }
	string map[n];
	for(int i=0; i<n; i++) cin >> map[i];
	
	bool v0[n][m];
	memset(v0, false, sizeof(bool)*n*m);
	
	bool v1[n][m];
	memset(v1, false, sizeof(bool)*n*m);
	
	queue<A> q;
	v0[0][0] = true;
	q.push(A(0, 0, 1, 1));
	
	while(!q.empty()) {
		int x = Q.x;
		int y = Q.y;
		int z = Q.z;
		int value = Q.value+1;
		q.pop();
		
		for(int i=0; i<4; i++) {
			x += V[i];
			y += H[i];
			
			if(x>=0 && y>=0 && x<n && y<m) {
				
				if(x == n-1 && y == m-1) {
					if(min > value) min = value;
					continue;
				}
				
				if(map[x][y] == '1') {
					if(z == 1 && min > value) q.push(A(x, y, z-1, value));
				}
				else {
					if(z == 1) {
						if(!v1[x][y]) {
							if(min > value) q.push(A(x, y, z, value));
							v1[x][y] = true;
						}
					}
					else {
						if(!v0[x][y]) {
							if(min > value) q.push(A(x, y, z, value));
							v0[x][y] = true;
						}
					}
				}
			}
			
			x -= V[i];
			y -= H[i];
		}
	} 
    
    if(min <1e9) cout << min;
    else cout << -1;
}

 

풀이 : BFS

 

큐에 집어넣을 것을

좌표값 두개, 벽을 몇번 통과했는지, 몇개를 지나왔는지를 담는 값(자신 포함) 을 담는 구조체로 구현했습니다.

 

방문 중복 체크를 할 때는 두가지로 나누었습니다.

하나는 한번도 벽을 통과하지 않은 경우

나머지 하나는 한 번 벽을 통과한 경우로 나누었습니다.

 

00000

11101

00001

01111

00010

 

이렇게 존재한다고 하면,

 

방문 중복 체크를 하나만 한 경우

 

00000

11101

00001

01111

00010  

 

이렇게 가장 아랫줄의 가운데 0을

 

00000

11101

00001

01111

00010

 

정답인 경우보다 먼저 방문하므로,

이미 방문처리가 되었기 때문에

위의 경우는 가장 마지막에 도달할 수 없게 됩니다. (오류)

 

이를 방지하기 위해

벽을 뿌시지 않은 경우의 방문 중복,

벽을 뿌순 경우의 방문 중복으로 나누었습니다.

 

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

2206번: 벽 부수고 이동하기