★ [Brute Force - 비트마스크] 구슬 탈출 2

예제 입력 1

5 5

#####

#..B#

#.#.#

#RO.#

#####

예제 출력 1

1

예제 입력 2

7 7

#######

#...RB#

#.#####

#.....#

#####.#

#O....#

#######

예제 출력 2

5

예제 입력 3

7 7

#######

#..R#B#

#.#####

#.....#

#####.#

#O....#

#######

예제 출력 3

5

예제 입력 4

10 10

##########

#R#...##B#

#...#.##.#

#####.##.#

#......#.#

#.######.#

#.#....#.#

#.#.#.#..#

#...#.O#.#

##########

예제 출력 4

-1

예제 입력 5

3 7

#######

#R.O.B#

#######

예제 출력 5

1

예제 입력 6

10 10

##########

#R#...##B#

#...#.##.#

#####.##.#

#......#.#

#.######.#

#.#....#.#

#.#.##...#

#O..#....#

##########

예제 출력 6

7

예제 입력 7

3 10

##########

#.O....RB#

##########

예제 출력 7

-1

 

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

13460번: 구슬 탈출 2

- 10번 이하로 움직여 빨간 구슬을 빼낼 수 없으면 불가능한 경우로 처리해야하므로, 각 10회 이동 경우를 비트마스크로 로 처리하여 해당 케이스의 경우를 다 해본다.

 

- 직접 풀어보기.

 

[ 모범 답안 (출처 : code.plus 알고리즘 중급 강의) ]

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int dx[] = { 0,0,1,-1 };
int dy[] = { 1, -1, 0, 0 };

const int LIMIT = 10; // 10번까지만 이동하므로

// 최대 10회의 이동 방법을 10개의 4진법 수로 변환
vector<int> gen(int k)
{
	vector<int> a(LIMIT);

	for (int i = 0; i < LIMIT; i++)
	{
		a[i] = (k & 3);	// 00,01,10,11
		k = k >> 2;			// 그 다음 처리	
	}

	return a;
}

bool valid(vector<int>& dir)
{
	int l = dir.size();

	for (int i = 0; i + 1 < l; i++)
	{
		if (dir[i] == 0 && dir[i + 1] == 1) return false;
		if (dir[i] == 1 && dir[i + 1] == 0) return false;
		if (dir[i] == 2 && dir[i + 1] == 3) return false;
		if (dir[i] == 3 && dir[i + 1] == 2) return false;
		if (dir[i] == dir[i + 1]) return false;
	}

	return true;
}

pair<bool, bool> simulate(vector<string>& a, int k, int& x, int& y)
{
	// 구슬이 움직여서 구멍에 빠질 경우 .가 되는데 이 경우를 고려
	if (a[x][y] == '.') return make_pair(false, false);

	int n = a.size();
	int m = a[0].size();

	bool moved = false;

	// 더이상 못움직일때까지
	while (true)
	{
		int nx = x + dx[k];
		int ny = y + dy[k];

		if (a[nx][ny] == '#') return make_pair(moved, false);
		else if(a[nx][ny] == 'R' || a[nx][ny] == 'B') return make_pair(moved, false);
		else if (a[nx][ny] == '.')
		{
			swap(a[nx][ny], a[x][y]); // 움직이려는 칸이 빈칸 - 움직이면 둘이 바뀐다.
			x = nx;
			y = ny;

			moved = true;
		}
		else if (a[nx][ny] == 'O')
		{
			a[x][y] = '.';
			moved = true;
			return make_pair(moved, true);
		}
	}

	// 이 경우는 실제로 없다.
	return make_pair(false, false);
}

int check(vector<string> a, vector<int>& dir)
{
	int n = a.size();
	int m = a[0].size();

	int hx, hy, rx, ry, bx, by; // 구멍,빨강,파랑구슬 위치

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (a[i][j] == 'O')
			{
				hx = i; hy = j;
			}
			else if (a[i][j] == 'R')
			{
				rx = i; ry = j;
			}
			else if (a[i][j] == 'B')
			{
				bx = i; by = j;
			}
		}
	}

	int cnt = 0;
	for (int k : dir)
	{
		cnt += 1;
		bool hole1 = false, hole2 = false;

		while (true)
		{
			auto p1 = simulate(a, k, rx, ry); // 빨간구슬 이동
			auto p2 = simulate(a, k, bx, by); // 파란구슬 이동

			// 둘다 안움직이면 나옴
			if (p1.first == false && p2.first == false)
				break;

			if (p1.second) hole1 = true;
			if (p2.second) hole2 = true;
		}

		if (hole2) return -1;
		if (hole1) return cnt;
	}

	return -1;
}

int main(void)
{
	int n, m;
	cin >> n >> m;

	vector<string> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];

	int ans = -1;

	// k는 1 << (LIMIT * 2) = 총 4^10 = 2^20의 경우의 수가 있다.
	for (int k = 0; k < (1 << (LIMIT * 2)); k++)
	{
		vector<int> dir = gen(k);

		/*
		기울이는 동작에서, 같은 방향으로 두번할 필요 없다.
		한쪽으로 기울이고 다시 반대쪽으로 기울일 필요 없다. 
		이 경우를 제외하여 경우의 수를 줄인다.
		경우의 수 = 4 x 2 x 2 x ... = 4 x 2^9 가 된다.
		*/
		if (!valid(dir)) continue; 

		int cur = check(a, dir);
		if (cur == -1) continue;
		if (ans == -1 || ans > cur) ans = cur;
	}

	cout << ans << '\n';

	return 0;
}