[백준] 13460번 구슬 탈출 2 (C++) - 1

13460번: 구슬 탈출 2

▷다른 방식 풀이 보러가기

 

상, 하, 좌, 우 방향으로 굴리면서 DFS 한다.

 

빨간 구슬과 파란 구슬이 일직선 상에 있을 경우

order 함수를 통해서 어느 구슬 먼저 굴려야 할지 판단해준 뒤

그 순서에 따라서 다음 경우에 맞게 처리해준다.

 

1. 빨간 구슬이 구멍에 들어가건 안 들어가건 상관없이

파란 구슬이 구멍 안으로 들어가는 경우

-> 실패이므로 구슬들의 위치만 원 상태로 복귀 후

다음 방향으로 넘어감(continue)

 

2. 파란 구슬이 구멍에 들어가지 않았고

빨간 구슬이 구멍에 들어가는 경우

-> 성공이므로 최소 횟수 갱신하고 구슬들의 위치 원 상태로 복귀 후

다음 방향으로 넘어감(continue)

 

3. 두 구슬이 모두 움직이지 않은 경우

-> 다음 방향으로 넘어감(continue)

 

4. 두 구슬이 정상적으로 굴러가고 구멍에도 빠지지 않은 경우

-> 횟수를 + 1 하고 다음 단계로 넘어감(재귀)

이때, 예를 들어 위쪽으로 굴러갔는데 거기서 다시 아래쪽으로 구르면

원점으로 돌아오는 것이므로

재귀 호출할 때 이전에 어떤 방향에서 왔는지도 같이 전달해주면

그 방향으로는 가지 않게 해 준다.

 

5. 굴리는 횟수가 11번 이상일 경우

-> 더 이상 연산하지 않고 return

 

모든 연산이 끝난 후

최솟값이 갱신되지 않았다면 -1 출력,

갱신되었다면 그 값을 출력한다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, Min = 11, Rx, Ry, Bx, By;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
char board[11][11];
vector <pair<int, int>> ball;
bool MoveR(int i) {
	while (1) {
		Rx += dx[i], Ry += dy[i];
		if (board[Rx][Ry] == 'O') return true;
		else if ((Rx == ball[1].first && Ry == ball[1].second) || board[Rx][Ry] == '#') {
			Rx -= dx[i], Ry -= dy[i];
			return false;
		}
	}
}
bool MoveB(int i) {
	while (1) {
		Bx += dx[i], By += dy[i];
		if (board[Bx][By] == 'O') return true;
		else if ((Bx == ball[0].first && By == ball[0].second) || board[Bx][By] == '#') {
			Bx -= dx[i], By -= dy[i];
			return false;
		}
	}
}
bool order(int i, int rx, int ry, int bx, int by) { //return값이 true면 빨간 구슬부터, false면 파란 구슬부터
	switch (i)
	{
	case(0): //상
		if (ry == by) if (rx < bx) return true;
		break;
	case(1): //하
		if (ry == by) if (rx > bx) return true;
		break;
	case(2): //좌
		if (rx == bx) if (ry < by) return true;
		break;
	case(3): //우
		if (rx == bx) if (ry > by) return true;
		break;
	}
	return false;
}
void Dfs(int cnt, int j) {
	if (cnt == 11) return;
	for (int i = 0; i < 4; i++) {
		if ((j == 0 && i == 1) || (j == 1 && i == 0) || (j == 2 && i == 3) || (j == 3 && i == 2)) continue; //이전에 왔던 방향으로 가는 것을 방지하기 위해
		Rx = ball[0].first, Ry = ball[0].second, Bx = ball[1].first, By = ball[1].second;
		int tmp_Rx = Rx, tmp_Ry = Ry, tmp_Bx = Bx, tmp_By = By;
		if (order(i, Rx, Ry, Bx, By)) {
			if (MoveR(i)) {
				ball[0].first = Rx, ball[0].second = Ry;
				if (!MoveB(i)) Min = min(Min, cnt); //성공 시 최솟값 갱신
			}
			else {
				ball[0].first = Rx, ball[0].second = Ry;
				if (!MoveB(i)) {
					if (ball[0].first == tmp_Rx && ball[0].second == tmp_Ry && ball[1].first == Bx && ball[1].second == By) continue; //둘 다 움직이지 않을 경우 다음 방향으로 넘어감
					ball[1].first = Bx, ball[1].second = By; //둘 다 정상적으로 움직일 경우 다음 차례로 넘어감
					Dfs(cnt + 1, i);
				}
			}
		}
		else {
			if (!MoveB(i)) {
				ball[1].first = Bx, ball[1].second = By;
				if (MoveR(i)) Min = min(Min, cnt); //성공 시 최솟값 갱신
				else {
					if (ball[0].first == Rx && ball[0].second == Ry && ball[1].first == tmp_Bx && ball[1].second == tmp_By) continue; //둘 다 움직이지 않을 경우 다음 방향으로 넘어감
					ball[0].first = Rx, ball[0].second = Ry; //둘 다 정상적으로 움직일 경우 다음 차례로 넘어감
					Dfs(cnt + 1, i);
				}
			}
		}
		ball[0].first = tmp_Rx, ball[0].second = tmp_Ry, ball[1].first = tmp_Bx, ball[1].second = tmp_By;
	}
}
int main() {      
	string a;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> a;
		for (int j = 0; j < M; j++) {
			if (a[j] == 'R') Rx = i, Ry = j;
			else if (a[j] == 'B') Bx = i, By = j;
			board[i][j] = a[j];
		}
	}
	ball.push_back(make_pair(Rx, Ry));
	ball.push_back(make_pair(Bx, By));
	Dfs(1, -1);
	if (Min == 11) cout << -1;
	else cout << Min;
	return 0;
}