구슬 탈출 2 (feat. 백준, 13460번)

구슬 탈출 2
https://www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

반응형

// woohyeon.kim
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int N, M;
int dx[4], dy[4];
bool visit[11][11];
char maps[11][11];

class Marble
{
public:
	const bool operator==(const Marble& value)
	{
		if (rx == value.rx && ry == value.ry && bx == value.bx && by == value.by)		return true;
		return false;
	}
	bool overlap()
	{
		if (rx == bx && ry == by)		return true;
		return false;
	}

public:
	int rx;
	int ry;
	int bx;
	int by;
	int count;
};

void bfs(Marble& marble)
{
	int result = static_cast<int>(1e9);
	queue<Marble> q;
	q.push(marble);

	Marble next_marble;
	while (!q.empty())
	{
		auto current_marble = q.front(); q.pop();
		if (current_marble.count == 10)
			continue;
		for (auto idx = 0; idx < 4; ++idx)
		{
			auto goal_red = false, goal_blue = false;
			next_marble = Marble{ current_marble.rx, current_marble.ry, current_marble.bx, current_marble.by, current_marble.count + 1 };
			// 빨간공 굴리기
			while (true)
			{
				auto nx = next_marble.rx + dx[idx]; auto ny = next_marble.ry + dy[idx];
				if (maps[nx][ny] == '#')
					break;
				else if (maps[nx][ny] == 'O')
				{
					goal_red = true;
					break;
				}
				next_marble.rx = nx, next_marble.ry = ny;
			}
			// 파란공 굴리기
			while (true)
			{
				auto nx = next_marble.bx + dx[idx]; auto ny = next_marble.by + dy[idx];
				if (maps[nx][ny] == '#')
					break;
				else if (maps[nx][ny] == 'O')
				{
					goal_blue = true;
					break;
				}
				next_marble.bx = nx, next_marble.by = ny;
			}
			// 빨간공이나 파란공이 들어갔으면
			if (goal_red || goal_blue)
			{
				// 빨간공만 들어갔으면
				if (!goal_blue)
					result = min(result, next_marble.count);
				continue;
			}

			// 빨간공 파란공이 겹쳐있으면
			if (next_marble.overlap())
			{
				switch (idx)
				{
				case 0:		// 남
					// 빨간공이 더 멀리 움직였으면 -> 빨간공 아래에 파랑이 있어야함
					if (abs(current_marble.rx - next_marble.rx) > abs(current_marble.bx - next_marble.bx))		next_marble.rx -= 1;
					else																						next_marble.bx -= 1;
					break;
				case 1:		// 북
					// 빨간공이 더 멀리 움직였으면 -> 빨간공 위에 파랑이 있어야함
					if (abs(current_marble.rx - next_marble.rx) > abs(current_marble.bx - next_marble.bx))		next_marble.rx += 1;
					else																						next_marble.bx += 1;
					break;
				case 2:		// 동
					// 빨간공이 더 멀리 움직였으면 -> 빨간공 오른쪽에 파랑이 있어야함
					if (abs(current_marble.ry - next_marble.ry) > abs(current_marble.by - next_marble.by))		next_marble.ry -= 1;
					else																						next_marble.by -= 1;
					break;
				case 3:		// 서
					// 빨간공이 더 멀리 움직였으면 -> 빨간공 왼쪽에 파랑이 있어야함
					if (abs(current_marble.ry - next_marble.ry) > abs(current_marble.by - next_marble.by))		next_marble.ry += 1;
					else																						next_marble.by += 1;
					break;
				}
			}
			// 현재 위치와 움직인 뒤의 위치가 같으면 -> 안움직였으면
			if (current_marble == next_marble)
				continue;
			q.push(next_marble);
		}
	}

	if (result == static_cast<int>(1e9))
		cout << -1 << endl;
	else
		cout << result << endl;
}

int main()
{
	Marble marble{ 0, 0, 0, 0, 0 };
	dx[0] = 1, dx[1] = -1, dx[2] = 0, dx[3] = 0;
	dy[0] = 0, dy[1] = 0, dy[2] = 1, dy[3] = -1;

	cin >> N >> M;
	for (auto ix = 0; ix < N; ++ix)
	{
		for (auto iy = 0; iy < M; ++iy)
		{
			cin >> maps[ix][iy];
			if (maps[ix][iy] == 'R')
			{
				marble.rx = ix, marble.ry = iy;
				maps[ix][iy] = '.';
			}
			else if (maps[ix][iy] == 'B')
			{
				marble.bx = ix, marble.by = iy;
				maps[ix][iy] = '.';
			}
		}
	}

	bfs(marble);

	return 0;
}
// *&)*@*

기존에 풀었던 형태와는 조금 달랐습니다.

조합이나 순열도 아니고, 두개의 공을 동시에 움직인다는 조건이 굉장히 까다로웠습니다.

질문에서 힌트를 얻은 것은 "빨간공과 파란공 서로가 없다고 생각하고, 만약에 겹친다면 움직인 거리에 따라서 빨간공 파란공 위치를 옮겨라" 였습니다.

​

1. 최초 R,B의 좌표를 구하고 해당 자리는 . 으로 변경해 버립니다.
2. 상하좌우 를 움직일때마다 조건들을 비교하면서 움직인 경우에 한해서만 bfs 대상이 됩니다. 단, 빨간공과 파란공이 겹치는 경우, 최초 위치에서 움직인 위치까지의 거리를 통해, 그리고 현재 내가 상하좌우 중 어디로 흔들었는지를 통해 빨간공이나 파란공의 위치를 옮겨줍니다.
3. 여기서 중요한건 옮겨진 위치가 최초 위치와 같다면, 사실 움직이지 않은 것이기 때문에 bfs 대상이 되지 않습니다.
4. 그 뒤 로직은 동일하고, O에 들어갔을때, 파란공은 들어가지 않았을때만 count를 가지고 있습니다.
5. 모든 조건에 대해서 체크가 끝나면 빨간공만 O에 들어갔을때의 count가 남게 됩니다.