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

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

13460번: 구슬 탈출 2

 

 

솔루션

---

역시나 시물레이션은 시간이 걸리고, 귀찮은 문제이다....

 

먼저. 구슬을 4 방향으로 굴릴 수 있는데, 한 번 기울이면 끝까지 굴려야 한다...

구슬을 굴릴 때 나는 조건을 세웠는데,

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

이 배열을 통해

인자를 던져서, 

각 방향으로 while문을 돌려줍니다!

1) 빨간 공이 O를 만나면

   - 파란공을 굴려서 O를 만나거나,

   - 벽을 만나거나('#')

 하면 그 좌표 값을 리턴을 해 줍니다.

 

2) 빨간 공이 '#'을 만나면,

   -파란공을 굴려서 'O'를 만나거나

   - 벽을 만났을 때

      `빨간 공과 위치가 같다면, dx,dy를 빼 줍니다.( 즉 한단계 이전으로 돌림)

그리고 리턴을 해 줍니다.

 

3) 빨간공이 전진하다 파란공을 만나면,

   -파란공을 먼저 굴려 벽을 만나면 빨간공의 좌표는 파란공-dx,파란공-dy

   - 파란공이 구멍을 만나면 빨간 공과 위치를 같게 함

그리고 리턴,

 

그리고 main문에서는 방문배열을 통해서 방문하지 않았고, 파란공이 구멍에 있지 않다면,

queue에 삽입을 해서 bfs를 돌려 주었습니다.

 

129번째 줄에 is_blue의 4차원 배열은, 빨간공의 좌표일때(2차원), 파란공의 해당 자리에(2차원) 간 적이

있는지 없는지 비교하기 위해서 입니다.

(2차원으로 방문배열을 하니 아래의 예시가 통과가 되지 않았습니다 ㅠ)

8 8
########
#.####.#
#...#B##
#.##.R.#
######.#
##.##O.#
###.##.#
########

 

 

그리고 함수의 인자는 &로 받아서 함수에서 while문을 돌려 좌표를 돌려 수정해 주어서 4개의 좌표를 

한번에 바꿀 수 있도록 하였습니다!

 

 

 

코드

---

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
char arr[12][12];
bool is_visit[12][12];
bool is_blue[12][12][12][12];
queue<pair<int, int>> B;
queue<pair<int, int>> R;
queue<int> T;
int N, M;
bool is_ball = false;
void moveBall(int i, int& rx, int& ry, int& bx, int& by) {
	//공을 굴리면서 확인해야 할 것
	//1. 벽에 닿을 때 까지,
	//3. 다른 공이 서있는 앞까지,
	while (true) {
		 if (arr[rx][ry] == 'O') {
			while (true) {
				//파란공이 멈추는 경우
				//벽에 닿거나, 구멍에 들어가거나,
				//빨간 공과 닿았을 경우.
				if (arr[bx + dx[i]][by + dy[i]] == '#') {
					break;
				}
				else if (arr[bx][by] == 'O') break;
				else {
					bx += dx[i]; by += dy[i];
					//만약 같으면 구멍에 빠진 것이니,
					//-1을 출력 할 것임.
				}
			}
			return;
		 }
		 else if (arr[rx + dx[i]][ry + dy[i]] == '#') {
			 while (true) {
				 //파란공이 멈추는 경우
				 //벽에 닿거나, 구멍에 들어가거나,
				 //빨간 공과 닿았을 경우.
				 if (arr[bx + dx[i]][by + dy[i]] == '#') {
					 break;
				 }
				 else if (arr[bx][by] == 'O') break;
				 else {
					 bx += dx[i]; by += dy[i];
					 if (bx == rx && by == ry) {
						 //빨간 공과 닿았으면 이전으로 돌리고 
						 //break;
						 bx -= dx[i]; by -= dy[i];
						 break;
					 }
				 }
			 }
			 //빨간 것도 벽이고, 파란것도 멈췄으면 return;
			 return;
		 }
		else if(rx+dx[i]==bx && ry+dy[i]==by) {
			//앞에 blue가 있다면,
			//blue먼저 다 움직여 줘야 함.
			while (true) {
				//파란공이 멈추는 경우
				//벽에 닿거나, 구멍에 들어가거나,
				//빨간 공과 닿았을 경우.
				if (arr[bx + dx[i]][by + dy[i]] == '#') {
					break;
				}
				else if (arr[bx][by] == 'O') {
					rx = bx; ry = by;
					return;
					break;
				}
				else {
					bx += dx[i]; by += dy[i];
				}
			}//레드 공은 블루 한칸 전에 있으므로
			rx = bx - dx[i]; ry = by - dy[i];
			is_ball = true;
			return;
		}
		else {
			rx += dx[i]; ry += dy[i];
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++ ) {
			cin >> arr[i][j];
			if (arr[i][j] == 'R') {
				R.push({ i,j });
				is_visit[i][j] = true;
			}
			else if (arr[i][j] == 'B') {
				B.push({ i,j });
			}
		}
	}
	T.push(0);
	int time = T.front();
	bool is_possible = false;
	while (!R.empty()) {
		int rx = R.front().first;
		int ry = R.front().second;
		int bx = B.front().first;
		int by = B.front().second;
		time = T.front();
		R.pop(); B.pop(); T.pop();

		if (time > 10 || arr[rx][ry]=='O') {
			if (arr[bx][by] == 'O' || time > 10) {
				time = -1;
			}
			is_possible = true;
			break;
		}
		for (int i = 0; i < 4; i++) {
			int Trx = rx, Try = ry;
			int Tbx = bx, Tby = by;
			moveBall(i, Trx, Try, Tbx, Tby);
			if (!(is_visit[Trx][Try] && is_blue[Trx][Try][Tbx][Tby])) {
				//방문하지 않은 지점 이라면,
				is_visit[Trx][Try] = true;
				is_blue[Trx][Try][Tbx][Tby] = true;
				if (arr[Tbx][Tby] == 'O') continue;
				R.push({ Trx,Try });
				B.push({ Tbx,Tby });
				T.push(time + 1);
			}
		}
	}
	if (!is_possible) {
		time = -1;
	}
	cout << time << "\n";

}