백준 13460 : 구슬 탈출 2 (Gold 1)

문제

---

백준 13460 : 구슬 탈출 2 (Gold 1)

문제 해석

---

시뮬레이션.

 

일반적인 미로 문제의 변형.

- 한번 출발한 방향으로 막힐 때까지 간다.

- 동시에 두 구슬이 움직인다.

- 파란 구슬이 떨어지면(출구에 도달) 안된다.

 

위 세가지만 유의하면 됩니다.

 

통찰

---

DP나 그리디와 달리 통찰이 필요 없습니다.

문제에서 요구하는 그대로 구현하면 됩니다.

 

처음에는 board전체를 복사하고 R과 B를 실제로 적는 식으로 하였는데

복사에 너무 많은 시간이 들어서(n*m = 10*10) 보드는 그대로 두고 구슬의 위치만 기록하는 식으로 변경하였습니다.

 

시간 복잡도

---

시간 복잡도 = 4^10*max(n, m) = 상하좌우 * 깊이 10까지 bfs * 한번 기울일 때 최대 이동하는 거리 max(n, m)

n, m이 10일 때, 시간 복잡도는 4^10*10 = 2^10^2*10 = 1000^2*10 = 10,000,000. 즉 1천만입니다.

 

일반적으로 10억 회 단위 연산을 1초 만에 할 수 있습니다.

 

1천만 < 20억 = 2초 임으로 시간 안에 문제를 풀 수 있습니다. 

 

풀이

---

문제를 쉽게 풀기 위해 시뮬레이션 과정을 몇 가지 함수로 나누었습니다.

 

- 기울여서 움직이는 move함수

- move 함수를 호출하는 최대 10번까지 모든 방향으로 움직여보는 sim 함수 (bfs 재귀)

 

또 move는 참조형 변수를 매개변수 pos로 받아 구슬의 현재 위치를 반환하였습니다.

또 move는 bool을 반환하여 탐색이 더 필요한지 알려줍니다.

 

/**
 * @template file author kadrick (kbk2581553@gmail.com)
 *
 * author:amkorousagi (hasmi5452@gmail.com)
 */
#include <bits/stdc++.h>
using namespace std;
#define fastio                                                                 \
  ios::sync_with_stdio(false);                                                 \
  cin.tie(0);
#define endl '\n'

int n, m;
int m_min = INT_MAX;
vector<vector<char>> board;

enum {LEFT, RIGHT, UP, DOWN};
bool move(int dir, vector<int>& pos, int cnt) {
	if (cnt >= m_min) {
		return false;
	}

	vector<int> res(4);
	bool qb = false;
	bool qr = false;
	if (dir == LEFT) {
		for (int i = 1; pos[1] - i>=0; i++) {
			if (board[pos[0]][pos[1] - i] == '#') {
				res[0] = pos[0];
				res[1] = pos[1] - i + 1;
				break;
			}
			else if (board[pos[0]][pos[1] - i] == 'O') {
				qr = true;
			}
		}
		for (int i = 1; pos[3] - i >= 0; i++) {
			if (board[pos[2]][pos[3] - i] == '#') {
				res[2] = pos[2];
				res[3] = pos[3] - i + 1;
				break;
			}
			else if (board[pos[2]][pos[3] - i] == 'O') {
				qb = true;
			}
		}

		if (res[0] == res[2] && res[1] == res[3]) {
			if (pos[1] < pos[3]) {
				res[3] += 1;
			}
			else {
				res[1] += 1;
			}
		}

	}
	else if (dir == RIGHT) {
		for (int i = 1; pos[1] + i < m; i++) {
			if (board[pos[0]][pos[1] + i] == '#') {
				res[0] = pos[0];
				res[1] = pos[1] + i - 1;
				break;
			}
			else if (board[pos[0]][pos[1] + i] == 'O') {
				qr = true;
			}
		}
		for (int i = 1; pos[3] + i < m; i++) {
			if (board[pos[2]][pos[3] + i] == '#') {
				res[2] = pos[2];
				res[3] = pos[3] + i - 1;
				break;
			}
			else if (board[pos[2]][pos[3] + i] == 'O') {
				qb = true;
			}
		}

		if (res[0] == res[2] && res[1] == res[3]) {
			if (pos[1] < pos[3]) {
				res[1] -= 1;
			}
			else {
				res[3] -= 1;
			}
		}
	}
	else if (dir == UP) {
		for (int i = 1; pos[0] - i >=0; i++) {
			if (board[pos[0]-i][pos[1]] == '#') {
				res[0] = pos[0] - i + 1;
				res[1] = pos[1];
				break;
			}
			else if (board[pos[0]-i][pos[1]] == 'O') {
				qr = true;
			}
		}
		for (int i = 1; pos[2] - i >=0; i++) {
			if (board[pos[2]-i][pos[3]] == '#') {
				res[2] = pos[2]-i+1;
				res[3] = pos[3];
				break;
			}
			else if (board[pos[2]-i][pos[3]] == 'O') {
				qb = true;
			}
		}

		if (res[0] == res[2] && res[1] == res[3]) {
			if (pos[0] < pos[2]) {
				res[2] += 1;
			}
			else {
				res[0] += 1;
			}
		}
	}
	else if (dir == DOWN) {
		for (int i = 1; pos[0] + i < n; i++) {
			if (board[pos[0] + i][pos[1]] == '#') {
				res[0] = pos[0] + i - 1;
				res[1] = pos[1];
				break;
			}
			else if (board[pos[0] + i][pos[1]] == 'O') {
				qr = true;
			}
		}
		for (int i = 1; pos[2] + i >= 0; i++) {
			if (board[pos[2] + i][pos[3]] == '#') {
				res[2] = pos[2] + i - 1;
				res[3] = pos[3];
				break;
			}
			else if (board[pos[2] + i][pos[3]] == 'O') {
				qb = true;
			}
		}

		if (res[0] == res[2] && res[1] == res[3]) {
			if (pos[0] < pos[2]) {
				res[0] -= 1;
			}
			else {
				res[2] -= 1;
			}
		}
	}




	pos.clear();
	pos.assign(res.begin(), res.end());
	if (qb) {
		return false;
	}
	else {
		if (qr) {
			m_min = min(m_min, cnt);
			return false;
		}
		else {
			return true;
		}
	}
}

void sim( int cnt, vector<int>& pos) {
	if (cnt + 1 > 10) {
		return;
	}

	vector<int> p;
	for (int i = 0; i < 4; i++) {
		p.clear();
		p.assign(pos.begin(),pos.end());
		if (move(i, p, cnt+1)) {
			sim(cnt + 1, p);
		}
	}
}


int main(void) {
	fastio;
	cin >> n >> m;
	board.assign(n, vector<char>(m));
	vector<int> pos(4);
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < m; j++) {
			board[i][j] = s[j];
			if (s[j] == 'R') {
				board[i][j] = '.';
				pos[0] = i;
				pos[1] = j;
			}
			if (s[j] == 'B') {
				board[i][j] = '.';
				pos[2] = i;
				pos[3] = j;
			}
		}
	}

	sim(0, pos);
	if (m_min == INT_MAX) {
		cout << -1;
	}
	else {
		cout << m_min;
	}
	return 0;
}