[백준][13460] 구슬 탈출 2

이 포스트는 백준 사이트의 구슬 탈출 2 문제 풀이입니다.

문제

해결 과정

이 문제는 2개의 구슬이 굴러다니며 목표 지점에 빨간색 구슬을 먼저 도착시키는 것이 목표인 문제입니다.
문제의 규칙은 아래와 같습니다.

1. 빨간 색 구슬을 파란 색 구슬보다 먼저 목표지점에 도착해야 한다.
2. 두 구슬은 겹쳐질 수 없다.
3. 지형을 기울여 구슬이 움직일 때는 벽 혹은 또 다른 구슬이 부딪힐 때 까지 계속 구른다.

이 규칙을 지키며 시뮬레이션을 실행하고자
너비 우선 탐색을 사용하는 simulate_board 함수와
지정된 방향에 따라 구슬의 움직인 결과를 반환하는 move 함수로 나누어 구현하였습니다.

코드 구현

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

vector<vector<char>> board;

void input(int& red_row, int& red_col, int& blue_row, int& blue_col);
void simulate_board(int& red_row, int& red_col, int& blue_row, int& blue_col, int& answer);
tuple<int, int, int, int> move(int dir, int red_row, int red_col, int blue_row, int blue_col);

int main() {
	int red_row, red_col, blue_row, blue_col;
	input(red_row, red_col, blue_row, blue_col);

	int answer = -1;
	simulate_board(red_row, red_col, blue_row, blue_col, answer);

	cout << answer;

	return 0;
}

void input(int& red_row, int& red_col, int& blue_row, int& blue_col) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N, M;
	cin >> N >> M;

	board.assign(N, vector<char>(M, 0));

	for (int row = 0; row < N; ++row) {
		for (int col = 0; col < M; ++col) {
			cin >> board[row][col];
			if ('R' == board[row][col]) {
				red_row = row, red_col = col;
			}
			else if ('B' == board[row][col]) {
				blue_row = row, blue_col = col;
			}
		}
	}
}

void simulate_board(int& red_row, int& red_col, int& blue_row, int& blue_col, int& answer) {
	queue<tuple<int, int, int, int, int>> q;
	q.push({ red_row, red_col, blue_row, blue_col, 0 });

	bool visited[10][10][10][10];
	visited[red_row][red_col][blue_row][blue_col] = true;

	while (false == q.empty()) {
		auto [red_row, red_col, blue_row, blue_col, dist] = q.front();
		q.pop();

		if (dist >= 10) {
			answer = -1;
			break;
		}

		for (int dir = 0; dir < 4; ++dir) {
			auto [new_red_row, new_red_col, new_blue_row, new_blue_col]
				= move(dir, red_row, red_col, blue_row, blue_col);

			if (new_blue_row == -2 && new_blue_col == -2) {
				continue;
			}

			if (new_red_row == -1 && new_red_col == -1) {
				answer = dist + 1;
				return;
			}

			if (visited[new_red_row][new_red_col][new_blue_row][new_blue_col]) continue;
			visited[new_red_row][new_red_col][new_blue_row][new_blue_col] = true;
			q.push({ new_red_row, new_red_col, new_blue_row, new_blue_col, dist + 1 });
		}
	}
}

tuple<int, int, int, int> move(int dir, int red_row, int red_col, int blue_row, int blue_col) {
	int dir_row[4]{ -1, 1, 0, 0 };
	int dir_col[4]{ 0, 0, -1, 1 };

	auto [prev_red_row, prev_red_col, prev_blue_row, prev_blue_col]
		= make_tuple( red_row, red_col, blue_row, blue_col );

	while (true) {
		red_row += dir_row[dir];
		red_col += dir_col[dir];

		if (board[red_row][red_col] == '#') {
			red_row -= dir_row[dir];
			red_col -= dir_col[dir];
			break;
		}
		else if (board[red_row][red_col] == 'O') {
			red_row = -1;
			red_col = -1;
			break;
		}
	}

	while (true) {
		blue_row += dir_row[dir];
		blue_col += dir_col[dir];

		if (board[blue_row][blue_col] == '#') {
			blue_row -= dir_row[dir];
			blue_col -= dir_col[dir];
			break;
		}
		else if (board[blue_row][blue_col] == 'O') {
			blue_row = -2;
			blue_col = -2;
			break;
		}
	}

	if (red_row == blue_row && red_col == blue_col) {
		if (dir == 0) {
			if (prev_blue_row > prev_red_row) blue_row -= dir_row[dir];
			else red_row -= dir_row[dir];
		}
		else if (dir == 1) {
			if (prev_blue_row < prev_red_row) blue_row -= dir_row[dir];
			else red_row -= dir_row[dir];
		}
		else if (dir == 2) {
			if (prev_blue_col > prev_red_col) blue_col -= dir_col[dir];
			else red_col -= dir_col[dir];
		}
		else if (dir == 3) {
			if (prev_blue_col < prev_red_col) blue_col -= dir_col[dir];
			else red_col -= dir_col[dir];
		}
	}

	return { red_row, red_col, blue_row, blue_col };
}

실행 결과