1. [백준 13460번 / C++] 구슬 탈출 2

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

13460번: 구슬 탈출 2

 

백준에서 제공하는 삼성 SW 역량 테스트 첫번째 문제다. 첫번째 문제부터 너무 어려워서 당황했는데 1시반정도만에 어떻게든 풀었다.

 

문제 설명은 정말 단순하다. 예전에 레이튼 교수와 이상한 마을이라는 게임을 해본 사람이라면 알고 있을 그런 구슬 탈출 게임이다.

 

다만 조건이 있는데 여기서는 중요하다고 생각했던 조건들만 말하겠다.

 

1. 상하좌우로만 움직일 수 있다.

2. 빨간구슬과 파란구슬은 동시에 움직인다.

3. 빨간구슬이 빠지면 성공! 하지만 파란구슬이 들어간다면 실패한다.

4. 빨간구슬과 파란구슬은 당연히 같은 칸에 있을 수 없다.

5. 10번이상의 횟수가 걸릴 경우 -1을 출력한다.

 

내가 생각한 아이디어는 빨간 구슬과 파란 구슬을 그냥 상하좌우 정해진 방향에 따라 무작정 옮기고 그 이후에 후처리를 해주는 것이었다.

 

즉, 

 

if) 어느 구슬이든 구멍에 들어가는 경우

-> 빨간 구슬만 들어간 경우

-> 파란 구슬만 들어간 경우

-> 둘다 들어간 경우

 

if) 구멍에 들어가지 않은 경우

-> 빨간 구슬과 파란 구슬의 위치가 같을 경우

-> 빨간 구슬과 파란 구슬의 위치가 같지 않을 경우

 

인 것이다. 이를 구현한 코드는 다음과 같다.

 

#include<bits/stdc++.h>
using namespace std;
const int dy[] = {-1, 0, 1, 0};  
const int dx[] = {0, 1, 0, -1}; // 위, 오른, 아래, 왼 
int n, m, hy, hx, ry, rx, by, bx, ret = 1e9, flag;
struct Board{
	int ry = 0, rx = 0, by = 0, bx = 0;
	char a[11][11];
	
	bool move(int dir){
		int temp_ry = ry, temp_rx = rx, temp_by = by, temp_bx = bx;
		
		int rFlag = 0, bFlag = 0;
		while(true){ // 빨간 구슬 move
			int ny = temp_ry + dy[dir];
			int nx = temp_rx + dx[dir];
			if(ny <= 0 || ny >= n - 1 || nx <= 0 || nx >= m - 1 || a[ny][nx] == '#') break;
			if(a[ny][nx] == 'O'){
				temp_ry = ny;
				temp_rx = nx;
				rFlag = 1;
				break;
			}
			temp_ry = ny;
			temp_rx = nx;
		}
		while(true){ // 파란 구슬 move
			int ny = temp_by + dy[dir];
			int nx = temp_bx + dx[dir];
			if(ny <= 0 || ny >= n - 1 || nx <= 0 || nx >= m - 1 || a[ny][nx] == '#') break;
			if(a[ny][nx] == 'O'){
				temp_by = ny;
				temp_bx = nx;
				bFlag = 1;
				break;
			}
			temp_by = ny;
			temp_bx = nx;
		}

		if(rFlag || bFlag){ // 구멍에 들어감	 
			if(rFlag && bFlag){
				flag = 1;
				return false;
			}
			if(bFlag){
				flag = 1;
				return false;
			}
			if(rFlag) return true;
		}else{ // 구멍에 안들어감 
			if(temp_ry == temp_by && temp_rx == temp_bx){ // 위치가 같을 경우 이치에 맞게 재배치
				if(dir == 0){
					if(ry > by){
						temp_ry++;
					}else if(ry < by){
						temp_by++;
					}
				}else if(dir == 1){
					if(rx > bx){
						temp_bx--;
					}else if(rx < bx){
						temp_rx--;
					}
				}else if(dir == 2){
					if(ry > by){
						temp_by--;
					}else if(ry < by){
						temp_ry--;
					}
				}else if(dir == 3){
					if(rx > bx){
						temp_rx++;
					}else if(rx < bx){
						temp_bx++;
					}
				}
				ry = temp_ry;
				rx = temp_rx;
				by = temp_by;
				bx = temp_bx;
				return false;
			}else{ // 위치가 다르다면 이동 위치 반영
				ry = temp_ry;
				rx = temp_rx;
				by = temp_by;
				bx = temp_bx;
				return false;
			}
		}
	}
};

void go(Board c, int cnt){
	if(cnt > 10) return;
	if(cnt > ret) return;
	for(int i = 0; i < 4; i++){
		Board d = c;
		if(d.move(i)){ // 빨간 구슬만 탈출했다면 ret 갱신
			ret = min(ret, cnt);
			return;
		}else{ // 탈출하지 못했을 경우
			if(flag){ // 파란 구슬도 같이 빠져서 반영해선 안되는 경우
				flag = 0;
				continue;
			}else{
				go(d, cnt + 1); // 이동한 Board가 횟수 1회를 사용하고 다음 회차로 이동
			}
		}
	}
	return; 
}
int main(){
	cin >> n >> m;
	Board c;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> c.a[i][j];
			if(c.a[i][j] == 'R'){
				c.ry = i;
				c.rx = j;
			}else if(c.a[i][j] == 'B'){
				c.by = i;
				c.bx = j;
			}
		}
	}
	go(c, 1);
	
	if(ret > 10) cout << "-1\n";
	else cout << ret << "\n";
	return 0;
}