[백준/BOJ] 백준 15653번 : 구슬 탈출 4

www.acmicpc.net/problem/15653

15653번: 구슬 탈출 4

빨간색 구슬과 파란색 구슬의 위치를 기준으로 너비 우선 탐색을 하여 문제를 해결했다. 즉 discovered[10][10][10][10]와, depth[10][10][10][10]은 [빨간구슬의 행][빨간구슬의 열][파란구슬의 행][파란구슬의 열]일때의 정보이다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>
#include <queue>
using namespace std;

int n, m;
vector<string> board;
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

int Solve(pair<int, int> red_start, pair<int, int> blue_start)
{
	int discovered[10][10][10][10];
	int depth[10][10][10][10];
	queue<pair<pair<int, int>, pair<int, int>>> q;

	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
			for (int k = 0; k < 10; k++)
				for (int l = 0; l < 10; l++)
					discovered[i][j][k][l] = 0;

	discovered[red_start.first][red_start.second][blue_start.first][blue_start.second] = 1;
	depth[red_start.first][red_start.second][blue_start.first][blue_start.second] = 0;
	q.push(make_pair(make_pair(red_start.first, red_start.second), make_pair(blue_start.first, blue_start.second)));

	while (!q.empty())
	{
		pair<int, int> red_here = q.front().first;
		pair<int, int> blue_here = q.front().second;
		q.pop();

		if (board[red_here.first][red_here.second] == 'O' && board[blue_here.first][blue_here.second] != 'O')
			return depth[red_here.first][red_here.second][blue_here.first][blue_here.second];

		if (board[blue_here.first][blue_here.second] == 'O')
			continue;

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> red_there = red_here;
			pair<int, int> blue_there = blue_here;

			//왼쪽으로 움직일때
			if (i == 0)
			{
				//빨간색, 파란색 둘다 같은 행에 있을때
				if (red_there.first == blue_there.first)
				{
					//빨간색이 더 왼쪽에 있을때
					if (red_there.second < blue_there.second)
					{
						while (board[red_there.first][red_there.second] == '.')
							red_there.second--;

						if (board[red_there.first][red_there.second] != 'O')
							red_there.second++;

						while (board[blue_there.first][blue_there.second] == '.' && red_there != blue_there)
							blue_there.second--;

						if (board[blue_there.first][blue_there.second] != 'O')
							blue_there.second++;
					}

					//빨간색이 더 오른쪽에 있을때
					else
					{
						while (board[blue_there.first][blue_there.second] == '.')
							blue_there.second--;

						if (board[blue_there.first][blue_there.second] != 'O')
							blue_there.second++;

						while (board[red_there.first][red_there.second] == '.' && blue_there != red_there)
							red_there.second--;

						if (board[red_there.first][red_there.second] != 'O')
							red_there.second++;
					}
				}

				//다른 행에 있을때
				else
				{
					while (board[red_there.first][red_there.second] == '.')
						red_there.second--;

					if (board[red_there.first][red_there.second] != 'O')
						red_there.second++;

					while (board[blue_there.first][blue_there.second] == '.')
						blue_there.second--;

					if (board[blue_there.first][blue_there.second] != 'O')
						blue_there.second++;
				}
			}

			//위쪽으로 움직일때
			else if (i == 1)
			{
				//빨간색, 파란색 둘다 같은 열에 있을때
				if (red_there.second == blue_there.second)
				{
					//빨간색이 더 위쪽에 있을때
					if (red_there.first < blue_there.first)
					{
						while (board[red_there.first][red_there.second] == '.')
							red_there.first--;

						if (board[red_there.first][red_there.second] != 'O')
							red_there.first++;

						while (board[blue_there.first][blue_there.second] == '.' && red_there != blue_there)
							blue_there.first--;

						if (board[blue_there.first][blue_there.second] != 'O')
							blue_there.first++;
					}

					//빨간색이 더 아래쪽에 있을때
					else
					{
						while (board[blue_there.first][blue_there.second] == '.')
							blue_there.first--;

						if (board[blue_there.first][blue_there.second] != 'O')
							blue_there.first++;

						while (board[red_there.first][red_there.second] == '.' && blue_there != red_there)
							red_there.first--;

						if (board[red_there.first][red_there.second] != 'O')
							red_there.first++;
					}
				}

				//다른 열에 있을때
				else
				{
					while (board[red_there.first][red_there.second] == '.')
						red_there.first--;

					if (board[red_there.first][red_there.second] != 'O')
						red_there.first++;

					while (board[blue_there.first][blue_there.second] == '.')
						blue_there.first--;

					if (board[blue_there.first][blue_there.second] != 'O')
						blue_there.first++;
				}
			}

			//오른쪽으로 움직일때
			else if (i == 2)
			{
				//빨간색, 파란색 둘다 같은 행에 있을때
				if (red_there.first == blue_there.first)
				{
					//빨간색이 더 오른쪽에 있을때
					if (red_there.second > blue_there.second)
					{
						while (board[red_there.first][red_there.second] == '.')
							red_there.second++;

						if (board[red_there.first][red_there.second] != 'O')
							red_there.second--;

						while (board[blue_there.first][blue_there.second] == '.' && red_there != blue_there)
							blue_there.second++;

						if (board[blue_there.first][blue_there.second] != 'O')
							blue_there.second--;
					}

					//빨간색이 더 왼쪽에 있을때
					else
					{
						while (board[blue_there.first][blue_there.second] == '.')
							blue_there.second++;

						if (board[blue_there.first][blue_there.second] != 'O')
							blue_there.second--;

						while (board[red_there.first][red_there.second] == '.' && blue_there != red_there)
							red_there.second++;

						if (board[red_there.first][red_there.second] != 'O')
							red_there.second--;
					}
				}

				else
				{
					while (board[red_there.first][red_there.second] == '.')
						red_there.second++;

					if (board[red_there.first][red_there.second] != 'O')
						red_there.second--;

					while (board[blue_there.first][blue_there.second] == '.')
						blue_there.second++;

					if (board[blue_there.first][blue_there.second] != 'O')
						blue_there.second--;
				}
			}

			//아래쪽으로 움직일때
			else if (i == 3)
			{
				//빨간색, 파란색 둘다 같은 열에 있을때
				if (red_there.second == blue_there.second)
				{
					//빨간색이 더 아래쪽에 있을때
					if (red_there.first > blue_there.first)
					{
						while (board[red_there.first][red_there.second] == '.')
							red_there.first++;

						if (board[red_there.first][red_there.second] != 'O')
							red_there.first--;

						while (board[blue_there.first][blue_there.second] == '.' && red_there != blue_there)
							blue_there.first++;

						if (board[blue_there.first][blue_there.second] != 'O')
							blue_there.first--;
					}

					//빨간색이 더 위쪽에 있을때
					else
					{
						while (board[blue_there.first][blue_there.second] == '.')
							blue_there.first++;

						if (board[blue_there.first][blue_there.second] != 'O')
							blue_there.first--;

						while (board[red_there.first][red_there.second] == '.' && blue_there != red_there)
							red_there.first++;

						if (board[red_there.first][red_there.second] != 'O')
							red_there.first--;
					}
				}

				//다른 열에 있을때
				else
				{
					while (board[red_there.first][red_there.second] == '.')
						red_there.first++;

					if (board[red_there.first][red_there.second] != 'O')
						red_there.first--;

					while (board[blue_there.first][blue_there.second] == '.')
						blue_there.first++;

					if (board[blue_there.first][blue_there.second] != 'O')
						blue_there.first--;
				}
			}

			if (discovered[red_there.first][red_there.second][blue_there.first][blue_there.second] == 1)
				continue;

			discovered[red_there.first][red_there.second][blue_there.first][blue_there.second] = 1;
			depth[red_there.first][red_there.second][blue_there.first][blue_there.second] = depth[red_here.first][red_here.second][blue_here.first][blue_here.second] + 1;
			q.push(make_pair(make_pair(red_there.first, red_there.second), make_pair(blue_there.first, blue_there.second)));
		}
	}

	//불가능할 경우
	return -1;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	pair<int, int> red;
	pair<int, int> blue;
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		string input;
		cin >> input;

		for (int j = 0; j < m; j++)
		{
			if (input[j] == 'R')
			{
				red = make_pair(i, j);
				input[j] = '.';
			}

			else if (input[j] == 'B')
			{
				blue = make_pair(i, j);
				input[j] = '.';
			}
		}

		board.push_back(input);
	}

	cout << Solve(red, blue);

	return 0;
}