백준 13460 - 구슬 탈출2

문제링크

• 백준 13460

문제설명

• N x M 크기의 보드가 있고, 테두리는 모두 벽(#)으로 막혀 있다.
• 보드는 빈칸(.)들과 빨간구슬(R)과 파란구슬(B), 구멍(O)이 하나씩 있고, 보드를 상하좌우로 기울이는 동작이 가능하다.
• 기울이는 동작은 구슬이 더이상 움직이지 않을 때 까지 이다.
• 각각의 동작에서 공은 동시에 움직이며 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 동시에 빠져도 실패이다.
• 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 10번 이하로 움직여서 빼낼 수 없다면 -1을 출력한다.

입력

• 첫번째 줄에는 보드의 크기 N, M 이 주어진다.
• N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. (., #, O, R, B)로 이루어져 있다.

문제접근방향

• 보드를 기울이기 전에 빨간 구슬과 파란 구슬이 같은 행, 같은 열에 위치하고 있었다면 기울이는 방향으로 먼저 앞서 있는 구슬을 선택한다.
  • 보드를 기울이기 전에 구슬을 선택하는 로직을 먼저 진행한다.
  • 항상 빨간 구슬의 좌표와 파란 구슬의 좌표를 기록해야한다.
• 상하좌우 기울임에 대한 함수를 따로 구현하고, 움직이고 난 후 보드를 업데이트 하고, 공의 좌표를 반환한다.
• first_ball 을 보드에서 움직이고 난 후, second_ball 을 움직인다.
• 빨간 구슬 혹은 파란 구슬이 구멍에 빠지거나, 기울이는 동작을 10번을 초과하는 경우 백트래킹을 한다.
• 기울이기 이전 상태로 돌아간 후, 다음 기울임을 재귀적으로 구현한다.

구현

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

void find_red_blue_pos(vector<string>& board, int& rxpos, int& rypos, int& bxpos, int& bypos) {
	int n = board.size();
	int m = board[0].size();

	for (int r = 0; r < n; r++) {
		for (int c = 0; c < m; c++) {
			if (board[r][c] == 'R') {
				rxpos = r;
				rypos = c;
			}
			else if (board[r][c] == 'B') {
				bxpos = r;
				bypos = c;
			}
		}
	}
}

bool check_hole(vector<string>& board, int xpos, int ypos) {
	if (board[xpos][ypos] == 'O') return true;
	else return false;
}

// 먼저 기울였을 때 움직이게 할 공을 설정한다.
// 빨간공이면 0, 파란공이면 1 반환
int set_priority_ball(int dir, int rxpos, int rypos, int bxpos, int bypos) {

	// 상(0), 하(1), 좌(2), 우(3)
	switch (dir) {
	case 0:
		if (rypos == bypos) {
			if (rxpos < bxpos) return 0;
			else return 1;
		}
		else return 2;
		break;
	case 1:
		if (rypos == bypos) {
			if (rxpos > bxpos) return 0;
			else return 1;
		}
		else return 2;
		break;
	case 2:
		if (rxpos == bxpos) {
			if (rypos < bypos) return 0;
			else return 1;
		}
		else return 2;
		break;
	case 3:
		if (rxpos == bxpos) {
			if (rypos > bypos) return 0;
			else return 1;
		}
		else return 2;
		break;
	}
}

// 모든 기울임의 결과는 좌표를 반환한다.
// 벽이나 다른 색상의 구슬과 부딪힌 경우 이전 빈칸의 좌표를 반환
// 구멍에 위치하게 된 경우 구멍의 좌표를 반환
pair<int, int> move_up(vector<string>& board, int n, int m, int xpos, int ypos) {
	char color = board[xpos][ypos];

	for (int r = xpos; r >= 0; r--) {
		if (board[r][ypos] == '.') continue;
		if (board[r][ypos] == 'O') {
			board[xpos][ypos] = '.';
			return make_pair(r, ypos);
		}
		if (board[r][ypos] == '#' || (board[r][ypos]!='.' && board[r][ypos] != color)) {
			board[xpos][ypos] = '.';
			board[r + 1][ypos] = color;
			return make_pair(r + 1, ypos);
		}
	}
	cout << "Move up error\n";
}

pair<int, int> move_down(vector<string>& board, int n, int m, int xpos, int ypos) {
	char color = board[xpos][ypos];
	for (int r = xpos; r < n; r++) {
		if (board[r][ypos] == '.') continue;
		if (board[r][ypos] == 'O') {
			board[xpos][ypos] = '.';
			return make_pair(r, ypos);
		}
		if (board[r][ypos] == '#' || (board[r][ypos] != '.' && board[r][ypos] != color)) {
			board[xpos][ypos] = '.';
			board[r - 1][ypos] = color;
			return make_pair(r - 1, ypos);
		}
	}
	cout << "Move down error\n";
}

pair<int, int> move_left(vector<string>& board, int n, int m, int xpos, int ypos) {
	char color = board[xpos][ypos];
	for (int c = ypos; c >= 0; c--) {
		if (board[xpos][c] == '.') continue;
		if (board[xpos][c] == 'O') {
			board[xpos][ypos] = '.';
			return make_pair(xpos, c);
		}
		if (board[xpos][c] == '#' || (board[xpos][c] != '.' && board[xpos][c] != color)) {
			board[xpos][ypos] = '.';
			board[xpos][c + 1] = color;
			return make_pair(xpos, c + 1);
		}
	}
	cout << "Move left error\n";
}

pair<int, int> move_right(vector<string>& board, int n, int m, int xpos, int ypos) {
	char color = board[xpos][ypos];
	for (int c = ypos; c < m; c++) {
		if (board[xpos][c] == '.') continue;
		if (board[xpos][c] == 'O') {
			board[xpos][ypos] = '.';
			return make_pair(xpos, c);
		}
		if (board[xpos][c] == '#' || (board[xpos][c] != '.' && board[xpos][c] != color)) {
			board[xpos][ypos] = '.';
			board[xpos][c - 1] = color;
			return make_pair(xpos, c - 1);
		}
	}
	cout << "Move right error\n";
}

void update_board(vector<string>& board, int n, int m, int dir, int& xpos, int& ypos) {

	pair<int, int> npos;
	// 상(0), 하(1), 좌(2), 우(3)
	switch (dir) {
	case 0:
		npos = move_up(board, n, m, xpos, ypos);
		xpos = npos.first;
		ypos = npos.second;
		break;
	case 1:
		npos = move_down(board, n, m, xpos, ypos);
		xpos = npos.first;
		ypos = npos.second;
		break;
	case 2:
		npos = move_left(board, n, m, xpos, ypos);
		xpos = npos.first;
		ypos = npos.second;
		break;
	case 3:
		npos = move_right(board, n, m, xpos, ypos);
		xpos = npos.first;
		ypos = npos.second;
		break;
	}
}

void move_board_proc(vector<string>& board, int n, int m, int& rxpos, int& rypos, int& bxpos, int& bypos, int cnt, int& ans) {
	// 기저사례1
	// 파란 구슬이 빠진 경우 (빨간 구슬과 파란 구슬이 동시에 빠져도 실패이므로 먼저 체크해야함)
	if (check_hole(board, bxpos, bypos)) return;
	// 기저사례2: 빨간 구슬이 빠진 경우
	if (check_hole(board, rxpos, rypos)) {
		if (ans > cnt) ans = cnt;
		return;
	}
	// 기저사례3: 10번을 초과하여 기울인 경우
	if (cnt == 10) return;

	for (int dir = 0; dir < 4; dir++) {
		vector<string> cur_board = board; // 기울이기 전 보드
		int c_rxpos = rxpos, c_rypos = rypos, c_bxpos = bxpos, c_bypos = bypos;
		int prior = set_priority_ball(dir, rxpos, rypos, bxpos, bypos);
		if (prior == 0) {
			update_board(board, n, m, dir, rxpos, rypos);
			update_board(board, n, m, dir, bxpos, bypos);
		}
		else {
			update_board(board, n, m, dir, bxpos, bypos);
			update_board(board, n, m, dir, rxpos, rypos);
		}
		move_board_proc(board, n, m, rxpos, rypos, bxpos, bypos, cnt + 1, ans);
		board = cur_board;
		rxpos = c_rxpos, rypos = c_rypos, bxpos = c_bxpos, bypos = c_bypos;
	}
}

// Debugging
void print_board(vector<string>& board) {
	for (auto ele : board)
		cout << ele << endl;
	cout << endl;
}

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

	int n, m;
	cin >> n >> m;

	vector<string> board;
	string str;
	for (int line = 0; line < n; line++) {
		cin >> str;
		board.push_back(str);
	}

	int rxpos, rypos, bxpos, bypos;
	int ans = 100;
	find_red_blue_pos(board, rxpos, rypos, bxpos, bypos);
	move_board_proc(board, n, m, rxpos, rypos, bxpos, bypos, 0, ans);
	if (ans > 10)
		ans = -1;
	cout << ans << endl;
}