백준 13460 구슬탈출 2 C++ - BFS

구슬탈출 1과 유사하지만 살짝 다른점이 있는 문제이다.

컴퓨터스러운 문제에서 현실 세계 시뮬레이션 문제로 바뀐 듯한 느낌이다.

 

조건은 다음과 같다.

1. 구멍에는 빨간 구슬만 들어가야한다.(빨간 구슬이 들어간 후 파란 구슬이 들어가도 실패)

2. 10회를 초과해야하거나 초과해도 못들어가는 경우는 실패로 간주한다.

3. 구슬은 부딪혀도 상관없지만, 온전한 1칸을 차지하기 때문에 옆에 구슬이 있다면 더 이상 가지 못한다.

4. 구슬은 멈출 때(벽을 만나거나 다른 구슬을 만나거나 구멍에 들어갈 때) 까지 굴러간다.

 

문제 풀이는 간단하다.

BFS를 사용하여 빨간 구슬과 파란 구슬의 위치를 발전시켜나가면 된다.

하지만 중복되는 상태를 고려하지 않으면 무한 루프가 생기게 되므로 visit 배열을 4차원 [Ry][Rx][By][Bx]로 만든다.

물론 메모리를 조금 더 아끼기 위해 2차원으로 하는 방법도 있으나 머리를 쓰기 싫어서(...)4차원으로 했다.

어차피 MAX N, MAX M 은 10까지이기 때문이다.

 

고생한 점

1. 영어 대문자 O 가 구멍인데, VS2019 버젼에서는 0과 O가 구별이 잘 안가게 써져서

O를 자꾸 0으로 써서 왜! 오류가 나는지 1시간은 찾은 것 같다.

2. 끝까지 움직이는 것을 어떻게 처리하는지 고민했다. 이 경우 flag를 세워 둘 다 못움직이는 경우를 생각했다.

3. 빨간 구슬이 구멍에 들어간 경우 위치가 그대로 남아서 파란 구슬이 구멍 직전까지만 움직이기 때문에, 

따로 처리해줘야 했다. 이 경우 파란 구슬의 다음 위치가 빨간 구슬의 현재 위치고, 빨간구슬이 구멍에 들어가 있다면

파란 구슬의 위치를 빨간 구슬과 같이 만들어줘 해결했다.

 

자세한 설명은 코드의 주석에 달려있다.

visited 배열은 [빨간구슬y][빨간구슬x][파란구슬y][파란구슬x]의 상태를 저장한다.

예를 들어 빨강(1,4) 파랑(2,5) 에 있다면 visited[1][4][2][5] = 1로 저장하여 중복 상태를 방지한다.

 

속도를 위해 BFS가 처음 구멍에 빠지면 즉시 리턴하고, 지금까지 움직인 횟수가 10회 이상이면 

구멍엔 11회 이상일 때 들어가기 때문에 바로 리턴 시켰다.

 

전체 코드

#include <stdio.h>
#include <queue>

using namespace std;

#define MAX_N 10
#define MAX_M 10
int N, M;
char Map[MAX_N+1][MAX_M+1];
int visited[MAX_N + 1][MAX_M + 1][MAX_N + 1][MAX_M + 1];//빨간구슬, 파란구슬 방문
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };

typedef struct s {
	int by, bx, ry, rx, cnt;
}CO;

queue<CO> q;

int bfs(int by,int bx, int ry, int rx) {
	CO cur = { by,bx,ry,rx,0 };
	visited[ry][rx][by][bx] = 1;
	q.push(cur);
	while (!q.empty()) {
		cur = q.front(); q.pop();
		if (cur.cnt >= 10) return -1;
		for (int i = 0; i < 4; i++) {
			int R_ny = cur.ry;
			int R_nx = cur.rx;
			int B_ny = cur.by;
			int B_nx = cur.bx;
			int flag = 0;
            //구슬 i 방향으로 굴려보기
			while (1) {
				flag = 0;
				//빨간 구슬
				//구멍에 들어갔을 경우
				if (Map[R_ny][R_nx] == 'O') flag = 1;
				//벽이 아닐경우
				else if (Map[R_ny+dy[i]][R_nx+dx[i]] != '#') {
					//구슬위치 파란 구슬과 안겹칠때 갈 수 있음
					if ((R_ny+dy[i] != B_ny) ||( R_nx+dx[i] != B_nx)) {
						R_ny+=dy[i];
						R_nx+=dx[i];
					}
					//구슬위치 겹쳐서 못 갈 경우
					else {
						flag = 1;
					}
				}
				//벽일 경우 (못움직일 경우)
				else {
					flag = 1;
				}

				//파란구슬
                //파란구슬이 구멍에 빠질 경우
				if (Map[B_ny][B_nx] == 'O') flag += 1;
                //벽에 안막힐 경우
				else if (Map[B_ny+dy[i]][B_nx+dx[i]] != '#') {
                //빨간 구슬과 겹치지 않을 경우 굴러감
					if ((R_ny != B_ny+dy[i]) ||( R_nx != B_nx+dx[i])) {
						B_ny+=dy[i];
						B_nx+=dx[i];
					}
                    //빨간 구슬과 겹칠 경우
					else {
                    //겹치는데 빨간 구슬이 구멍에 들어갔을 경우 파란 구슬도 구멍에 빠짐
						if (Map[R_ny][R_nx] == 'O') {
							B_ny = R_ny;
							B_nx = R_nx;
						}
                        //구멍에 빠지지 않았다면 움직이지 못함
						flag += 1;
					}
				}
                //벽일 경우
				else { flag += 1; }

				//둘다 못움직일 경우
				if (flag >= 2) break;
				 
			}
            //파란 구슬이 구멍에 빠졌다면 안됨
			if (Map[B_ny][B_nx] == 'O') continue;
            //빨간 구슬이 구멍에 들어갔다면 종료
			if (Map[R_ny][R_nx] == 'O') return cur.cnt + 1;
			//중복된 상태일 경우 안됨
			if (visited[R_ny][R_nx][B_ny][B_nx]) continue;
			visited[R_ny][R_nx][B_ny][B_nx] = 1;
			CO tmp = { B_ny, B_nx, R_ny, R_nx, cur.cnt + 1 };
			q.push(tmp);
			
			
		}

	}
	return -1;
}


int solve() {
	int ret = 0;
	int ry=0,rx=0, by=0, bx=0;
    //구슬 위치 찾기
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (Map[i][j] == 'R') {
				ry = i;
				rx = j;
			}
			else if (Map[i][j] == 'B') {
				by = i;
				bx = j;
			}
		}
	}
	ret = bfs(by,bx,ry,rx);
	return ret;

}

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		scanf("%s", Map[i]);
	}
	int ans =solve();
	printf("%d", ans);
}