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

13460번: 구슬 탈출 2

▷다른 방식 풀이 보러가기

 

최대 10번 움직여서 빨간 구슬을 빼내야 하므로

상, 하, 좌, 우로 기울이는 순서를 1~10 까지 중복 순열로 지정한다.

대신, 같은 방향이 연속되지 않게 한다.

 

ex)

1번 움직일 경우 가능한 순서 : 

1) 상(↑)

2) 하(↓)

3) 좌(←)

4) 우(→)

 

2번 움직일 경우 가능한 순서 :

1) 상(↑) 하(↓)

2) 상(↑) 좌(←)

3) 상(↑) 우(→)

4) 하(↓) 상(↑) 

5) 하(↓) 좌(←)

6) 하(↓) 우(→)

...

11) 우(→) 하(↓)

12) 우(→) 좌(←)

 

3번 움직일 경우 가능한 순서 :

1) 상(↑) 하(↓) 상(↑) 

2) 상(↑) 하(↓) 좌(←)

3) 상(↑) 하(↓) 우(→)

4) 상(↑) 좌(←) 상(↑) 

5) 상(↑) 좌(←) 하(↓)

6) 상(↑) 좌(←) 우(→)

...

35) 우(→) 좌(←) 하(↓)

36) 우(→) 좌(←) 우(→)

 

이런 식으로 1번일 때부터 최대 10번까지 순서를 구한다.

 

r번 기울이는 순서를 구하면 move() 함수에서 그 순서대로 구슬을 움직인다.

이때 주의할 사항은

구슬은 동시에 움직인다는 조건이 있기 때문에

기울이는 방향을 향해 맨 앞에 있는 구슬부터 움직여 줘야 한다.

그래서 기울이는 방향에 따라 두 구슬의 위치를 정렬해주었다.

 

상(↑) : x 좌표가 더 큰 거부터

하(↓) : x 좌표가 더 작은 거부터

좌(←) : y 좌표가 더 작은 거부터

우(→) : y 좌표가 더 큰 거부터

 

r번일 때 해당 순서대로 움직여서 성공하면 r을 출력하면 된다.

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

int N, M, res = -1, d;
int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 };
char board[11][11];
vector<int>order; // 기울이는 순서 -> 중복 순열
vector<pair<int,int> > ball; // 맨 처음 빨간 구슬과 파란 구슬 위치 저장

bool compare(pair<int, int> a, pair<int, int> b) { // 기울이는 방향에 따라 정렬이 달라짐 (먼저 위치해 있는 구슬 구분 위해)
	if (d == 0) return a.first < b.first; 
	else if (d == 1) return a.first > b.first;
	else if (d == 2) return a.second < b.second;
	else return a.second > b.second;
}

bool move() {
	bool success = false;
	vector<pair<int, int> > tmp, tmp2; // tmp2는 갱신되는 구슬 위치 저장용
	char arr[11][11] = { 0 };
	copy(&board[0][0], &board[0][0] + 11 * 11, &arr[0][0]); // 배열 복사
	copy(ball.begin(), ball.end(), back_inserter(tmp)); // 벡터 복사

	for (int t = 0; t < order.size(); t++) {
		d = order[t];
		sort(tmp.begin(), tmp.end(), compare); // 기울이는 방향에 먼저 있는 구슬부터 움직일 거임
		for (int k = 0; k < 2; k++) {
			int x = tmp[k].first, y = tmp[k].second;
			char currentBall = arr[x][y];
			arr[x][y] = '.'; // 구슬 흔적 지워주기
			if (currentBall == 'B') { // 파란 구슬
				while (1) {
					x += dx[order[t]], y += dy[order[t]];
					if (arr[x][y] == '#' || arr[x][y] == 'R') { // 파란 구슬이 벽이나 빨간 구슬에 부딪히면
						x -= dx[order[t]], y -= dy[order[t]];
						arr[x][y] = 'B';
						tmp2.push_back({ x,y }); // 파란 구슬의 새로운 위치 갱신
						break;
					}
					else if (arr[x][y] == 'O') return false; // 파란 구슬이 구멍에 빠진다면 실패
				}
			}
			else { // 빨간 구슬
				while (1) {
					x += dx[order[t]], y += dy[order[t]];
					if (arr[x][y] == '#' || arr[x][y] == 'B') { // 빨간 구슬이 벽이나 파란 구슬에 부딪히면
						x -= dx[order[t]], y -= dy[order[t]];
						arr[x][y] = 'R';
						tmp2.push_back({ x,y }); // 빨간 구슬의 새로운 위치 갱신
						break;
					}
					else if (arr[x][y] == 'O') {
						success = true; // 구슬이 동시에 빠지면 실패니까 일단 체크만 해둠
						break;
					}
				}
			}
		}
		tmp.clear();
		copy(tmp2.begin(), tmp2.end(), back_inserter(tmp)); // 벡터 복사
		tmp2.clear();
	}
	if (success) return true; // 빨간 구슬만 빠졌다면 성공
	return false;
}

void permutation(int before, int cnt, int r) { // 중복 순열. 단, 이전 방향과 겹치지 않게
	if (cnt == r) {
		if (move()) res = r;
		return;
	}
	for (int i = 0; i < 4; i++) {
		if (before == i) continue; // 이전 방향과 같으면 넘김
		order.push_back(i);
		permutation(i, cnt + 1, r);
		if (res != -1) return; // 성공이면 빠져나옴
		order.pop_back();
	}
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> board[i][j];
			if (board[i][j] == 'R' || board[i][j] == 'B') ball.push_back({ i,j });
		}
	}
	for (int i = 1; i <= 10; i++) { // 1부터 10까지 뽑는 중복 순열
		permutation(-1, 0, i);
		if (res != -1) break; // 성공이면 빠져나옴
	}
	cout << res;
	return 0;
}