[BOJ] 13460 : 구슬 탈출 2 - travelbeeee

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

---

[ 알고리즘풀이 ]

1. 백트레킹을 이용해 10번 이동하는 모든 경우의 수를 구하기.

2. 각 경우의 수마다 구슬판을 기울여가며 빨간 구슬은 구멍에 빠지고, 파란 구슬은 구멍에 빠지지 않는 경우가 생긴다면 답을 갱신한다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int N, M, ans = 987654321;
char map[10][11] = {}, tempMap[10][11] = {};

void mapCopy(char tempMap[10][11]) {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			tempMap[i][j] = map[i][j];
	return;
}

void goLeft(int* x, int* y) {
	char temp = tempMap[*x][*y];
	tempMap[*x][*y] = '.';
	int j = *y;
	while (j--) {
		if (tempMap[*x][j] != '.')
			break;
	}
	if (tempMap[*x][j] == 'O'){
		*y = j;
	}
	else{
		*y = j + 1;
		tempMap[*x][*y] = temp;
	}
	return;
}

void goRight(int* x, int* y) {
	char temp = tempMap[*x][*y];
	tempMap[*x][*y] = '.';
	int j = *y;
	while (j++) {
		if (tempMap[*x][j] != '.')
			break;
	}
	if (tempMap[*x][j] == 'O') {
		*y = j;
	}
	else {
		*y = j - 1;
		tempMap[*x][*y] = temp;
	}
	return;
}

void goUp(int* x, int* y) {
	char temp = tempMap[*x][*y];
	tempMap[*x][*y] = '.';
	int i = *x;
	while (i--) {
		if (tempMap[i][*y] != '.')
			break;
	}
	if (tempMap[i][*y] == 'O') {
		*x = i;
	}
	else {
		*x = i + 1;
		tempMap[*x][*y] = temp;
	}
	return;
}

void goDown(int* x, int* y) {
	char temp = tempMap[*x][*y];
	tempMap[*x][*y] = '.';
	int i = *x;
	while (i++) {
		if (tempMap[i][*y] != '.')
			break;
	}
	if (tempMap[i][*y] == 'O') {
		*x = i;
	}
	else {
		*x = i - 1;
		tempMap[*x][*y] = temp;
	}
	return;
}
void playGame(vector<int> v) {
	mapCopy(tempMap);
	// 빨간구슬, 파란구슬 위치를 따자.
	int redX, redY, blueX, blueY;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (tempMap[i][j] == 'R')
				redX = i, redY = j;
			if (tempMap[i][j] == 'B')
				blueX = i, blueY = j;
		}
	}
	// 기울이기 10번을 진행.
	for (int i = 0; i < 10; i++) {
		if (i >= ans)
			break;
		if (v[i] == 1) { // 왼쪽으로 기울이자.
			if (redX == blueX && redY > blueY) { // 파랑부터기울이자.
				goLeft(&blueX, &blueY);
				goLeft(&redX, &redY);
			}
			else {
				goLeft(&redX, &redY);
				goLeft(&blueX, &blueY);
			}
		}
		else if (v[i] == 2) { // 오른쪽으로 기울이자.
			if (redX == blueX && redY < blueY) {
				goRight(&blueX, &blueY);
				goRight(&redX, &redY);
			}
			else {
				goRight(&redX, &redY);
				goRight(&blueX, &blueY);
			}
		}
		else if (v[i] == 3) { // 위로 기울이자.
			if (redY == blueY && redX < blueX) {
				goUp(&redX, &redY);
				goUp(&blueX, &blueY);
			}
			else {
				goUp(&blueX, &blueY);
				goUp(&redX, &redY);
			}
		}
		else { // 아래로 기울이자.
			if (redY == blueY && redX < blueX) {
				goDown(&blueX, &blueY);
				goDown(&redX, &redY);
			}
			else {
				goDown(&redX, &redY);
				goDown(&blueX, &blueY);
			}
		}
		// 게임이 끝났는지 안끝났는지 체크.	
		if (map[blueX][blueY] == 'O')
			break;
		if (map[redX][redY] == 'O' && map[blueX][blueY] != 'O') {
			ans = min(ans, i + 1);
			break;
		}
		
	}
	return;
}

void Backtracking(vector<int> v) {
	if (v.size() == 10) {
		playGame(v);
		return;
	}
	for (int i = 1; i <= 4; i++) {
		v.push_back(i);
		Backtracking(v);
		v.pop_back();
	}
}

void Init(void) {
	vector<int> v;
	Backtracking(v);
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++)
		cin >> map[i];

	Init();
	if (ans == 987654321)
		ans = -1;
	cout << ans;
	return 0;
}

알고리즘을 먼저 머리와 손으로 정리하고 구현해야하는데,,,,,,

남들보다 실행 시간도 오래걸리고 비효율적인 알고리즘 같다,,,,!!

반성 

---