[C++][BOJ] 삼성 SW 역량 테스트 기출 문제 - 13460번 구슬 탈출2

 

정답 코드

#include <iostream>
#include <utility>
#include <queue>
using namespace std;

#define MAX_MAP 11
char map[MAX_MAP][MAX_MAP];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int N, M;
pair<int, int> Red;
pair<int, int> Blue;
pair<int, int> Hole;
struct MapInfo
{
	pair<int, int> RedPos;
	pair<int, int> BluePos;
	int count;
};
int Solve()
{
	bool visited[MAX_MAP][MAX_MAP][MAX_MAP][MAX_MAP] = { false, }; //red와 blue의 각각 위치
	queue<MapInfo> q;
	MapInfo m;
	m.BluePos = Blue;
	m.RedPos = Red;
	m.count = 0;
	q.push(m);
	visited[m.RedPos.first][m.RedPos.second][m.BluePos.first][m.BluePos.second] = true;
	while (!q.empty())
	{
		MapInfo cur = q.front();

		int ry = cur.RedPos.first;
		int rx = cur.RedPos.second;
		int by = cur.BluePos.first;
		int bx = cur.BluePos.second;
		q.pop();

		if (cur.count > 10) return -1;

		if (ry == Hole.first && rx == Hole.second)
		{
			return cur.count;
		}
		//4방향으로 빈칸이 아닐때까지 이동
		for (int i = 0; i < 4; i++)
		{
			int n_ry = ry + dy[i];
			int n_rx = rx + dx[i];
			int n_by = by + dy[i];
			int n_bx = bx + dx[i];

			while (1)
			{
				if (map[n_ry][n_rx] == '#')
				{
					n_ry -= dy[i]; 
					n_rx -= dx[i];
					break;
				}
				if (map[n_ry][n_rx] == 'O') break;
				n_ry += dy[i]; 
				n_rx += dx[i];
			}
			while (1)
			{
				if (map[n_by][n_bx] == '#')
				{
					n_by -= dy[i];
					n_bx -= dx[i];
					break;
				}
				if (map[n_by][n_bx] == 'O') break;
				n_by += dy[i];
				n_bx += dx[i];
			}

			//파란 구슬이 구멍에 빠졌으면 다른 방향으로
			if (n_by == Hole.first && n_bx == Hole.second) continue;

			//같은 위치에 빨간색 구슬과 파란색 구슬이 있으면 위치를 조정해 줘야 함
			//RB, BR 케이스 처리
			//EX) RB인데 왼쪽이면 B가 한칸 오른쪽으로 가야함, BR인데 왼쪽이면 R이 한칸 오른쪽으로 가야함
			if (n_ry == n_by && n_rx == n_bx)
			{
				switch(i) {
				case 0: rx > bx ? n_rx++ : n_bx++; break;
				case 1: rx < bx ? n_rx-- : n_bx--; break;
				case 2: ry > by ? n_ry++ : n_by++; break;
				case 3: ry < by ? n_ry-- : n_by--; break;
				}
			}

			if (visited[n_ry][n_rx][n_by][n_bx]) continue;
			MapInfo temp;
			temp.BluePos = make_pair(n_by, n_bx);
			temp.RedPos = make_pair(n_ry, n_rx);
			temp.count = cur.count + 1;
			q.push(temp);
			visited[n_ry][n_rx][n_by][n_bx] = true;
		}
	}
	return -1;
}
int main()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 'R')
			{
				Red.first = i;
				Red.second = j;
			}
			else if (map[i][j] == 'B')
			{
				Blue.first = i;
				Blue.second = j;
			}
			else if (map[i][j] == 'O')
			{
				Hole.first = i;
				Hole.second = j;
			}
		}
	}

	cout << Solve() << endl;
}