백준 13460 구슬 탈출2

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

삼성 역량 테스트 기출문제를 풀려고 들어갔다가 맨 위에 있어서 풀었는데 생각보다 까다로운 문제였습니다 ㅠ ㅠ

빨간 구슬과 파란 구슬이 있는데 이 구슬들을 상하 좌우로 기울여서 구멍에 넣어야 하는데 이때 기울이는 최소의 회수를 구해야 합니다. 그러나 파란 구슬이 먼저 빠지거나, 동시에 빠지는 경우는 포함하지 않아야 합니다. 일단은 코드가 깁니다. 짧게 짜신 분들도 있으신거 같은데 이런저런 조건을 자꾸 넣다보니 코드가 길어졌습니다. 우선은 구슬이 2개이므로 2개다 움직이는 것을 생각해 주어야합니다. 저는 이 구슬들의 방문점을 체크하기 위해 4차원 배열을 잡았습니다. 그래서 빨간 구슬과 파란구슬의 시작 좌표는 방문한것으로 생각을 하였습니다. 그리고 빨간 구슬과 파란 구슬이 있는 좌표는 이동 불가이므로 그부분을 계속 채크해주며 진행 하였고 구멍에 빠진다면 종료를 파란색도 빠져 버린다면 그부분을 무효시키고 반복 하였습니다. 

 

다음은 코드입니다.

 

#include <iostream>
#include <string>
#include <queue>

using namespace std;

int visited[10][10][10][10]; // 빨강 파랑 xy좌표 세트를 방문한적이 있는가? 
int maze[10][10]; 
queue<pair<int, int>> q1; // 빨간 구슬 
queue<pair<int, int>> q2; // 파란 구슬 
int nextx[4] = {1, 0, -1, 0};
int nexty[4] = {0, 1, 0, -1};
int N,M; 
int n;
bool flag = false;
void bfs() {
	
	while(!q1.empty()) {
		int len = q1.size();
		
		for(int a = 0; a < len; a++) {
			int xr = q1.front().first;
			int yr = q1.front().second;
			int	xb = q2.front().first;
			int	yb = q2.front().second;
			
		
		for(int i = 0; i < 4; i++) {
			//시작 위치 이동 불능 
			maze[xr][yr] = 0;
			maze[xb][yb] = 0; 
			
			int xxr = xr + nextx[i];
			int yyr = yr + nexty[i];
			int xxb = xb + nextx[i];
			int yyb  =yb + nexty[i];
			
			if(n >= 10) {
				n = -1;
				return;	
			}
			
			for(int k = 0; k < 2; k++) { // 2회 반복 무엇이 우선인지 알수 없으므로 
				
				if(xxr > 0 && xxr < N-1 && yyr > 0 && yyr < M-1 && maze[xxr][yyr] == 1) {
					maze[xxr-nextx[i]][yyr-nexty[i]] = 1; // 원래 있던 위치 이동가능 
					 while(maze[xxr][yyr] == 1) {
						xxr += nextx[i];
						yyr += nexty[i];
					}
					maze[xxr-nextx[i]][yyr-nexty[i]] = 0; //새로운 위치 이동 불가능 
				}
				
				
				if(xxb > 0 && xxb < N-1 && yyb > 0 && yyb < M-1 && maze[xxb][yyb] == 1) {
					 maze[xxb-nextx[i]][yyb-nexty[i]] = 1;  //원래 위치 이동가능 
					 while(maze[xxb][yyb] == 1) {
						xxb += nextx[i];
						yyb += nexty[i];
					}
					maze[xxb-nextx[i]][yyb-nexty[i]] = 0; //새로운 위치 이동 불가능 
				}
				
					if(maze[xxr][yyr] == 2) {
						maze[xxr-nextx[i]][yyr-nexty[i]] = 1;
					}
			}	
				// 이동 종료후 원래 상황으로  
				maze[xxr-nextx[i]][yyr-nexty[i]] = 1;
				maze[xxb-nextx[i]][yyb-nexty[i]] = 1;
				
			
				if(maze[xxb][yyb] == 2) // 파란 구슬이 빠진경우 
					continue; 
			
				
				if(maze[xxr][yyr] == 2 && maze[xxb][yyb] != 2) { //빨간 구슬만 빠진경우 
					n++;
					flag = true;
					return;
				}
						
					
				if(visited[xxr-nextx[i]][yyr-nexty[i]][xxb-nextx[i]][yyb-nexty[i]] == 0) {
					visited[xxr-nextx[i]][yyr-nexty[i]][xxb-nextx[i]][yyb-nexty[i]] = 1;
					q1.push(make_pair(xxr-nextx[i],yyr-nexty[i])); 
					q2.push(make_pair(xxb-nextx[i],yyb-nexty[i]));
				}
				
			}
			//최종 이동 종료후 원래의 위치는 이동 가능 상태로 
			maze[xr][yr] = 1;
			maze[xb][yb] = 1;
			q1.pop();
			q2.pop();
		}
		n++;
	} 
	
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> N >> M;
	string str[10];
	
	for(int i = 0; i < N; i++) {
		cin>>str[i];
		for(int j = 0; j < str[i].size(); j++) {
			if(str[i][j] == '.') 
				maze[i][j] = 1; // 1은 이동 가능을 의미 
			else if(str[i][j] == 'R') 
				q1.push(make_pair(i, j));
			else if(str[i][j] == 'B')
				q2.push(make_pair(i, j));
			else if(str[i][j] == 'O') 
				maze[i][j] = 2; // 구멍 좌표 저장 
		}
	}
	visited[q1.front().first][q1.front().second][q2.front().first][q2.front().second] = 1;
	bfs();
	if(flag)
		cout<<n;
	else
		cout<<-1;
	return 0;
}