[백준/BOJ] 백준 13460번 : 구슬 탈출 2

2020. 8. 13. 02:40ㆍ알고리즘 문제풀이

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

 

13460번: 구슬 탈출 2

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'

www.acmicpc.net

빨간 구슬과 파란 구슬의 처음 위치에서 빨간 구슬만 출구로 탈출시키기 위해 움직여야 하는 최소 횟수를 bfs를 통해 구한다

 

코드

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

int n, m;
vector<string> board;
int discoverd[10][10][10][10];
int depth[10][10][10][10];

struct Red_Blue { //빨강구슬과 파란구슬의 위치를 저장할 구조체
	int red_x;
	int red_y;
	int blue_x;
	int blue_y;
};

void pre_discoverd()
{
	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++)
					discoverd[i][j][k][l] = 0;
}

//빨간구슬과 파란구슬의 처음위치에서 빨간구슬만 출구로 이동하기 위해 움직여야 하는 최소 횟수를 bfs를 통해 구한다
int Solve(Red_Blue red_blue_start, pair<int, int> exit)
{
	discoverd[red_blue_start.red_x][red_blue_start.red_y][red_blue_start.blue_x][red_blue_start.blue_y] = 1;
	depth[red_blue_start.red_x][red_blue_start.red_y][red_blue_start.blue_x][red_blue_start.blue_y] = 0;

	queue<Red_Blue> q;
	q.push(red_blue_start);

	while (!q.empty())
	{
		Red_Blue here = q.front();
		q.pop();

		//움직인 횟수가 10번을 넘었을때
		if (depth[here.red_x][here.red_y][here.blue_x][here.blue_y] > 10)
			return -1;

		//파란구슬이 출구 빠졌을때
		if (here.blue_x == exit.first && here.blue_y == exit.second)
			continue;

		//빨간구슬만 출구로 빠졌을때
		if (here.red_x == exit.first && here.red_y == exit.second)
			return depth[here.red_x][here.red_y][here.blue_x][here.blue_y];

		//왼쪽,위쪽,오른쪽,아래쪽으로 보드를 기울였을때 빨간 구슬과 파란 구슬의 위치(there)를 구해
		//발견한적이 없는 위치라면 큐에 넣는다
		//특정 방향으로 기울때, 기우는 쪽에 더 가까이 있는 구슬의 위치를 먼저 움직였다
		//예를들어 왼쪽으로 기울때 빨간구슬이 파란구슬보다 더 왼쪽에 있다면 빨간구슬 먼저 움직였다
		for (int i = 0; i < 4; i++)
		{
			Red_Blue there;

			if (i == 0) //왼쪽으로 기울기
			{
				there = here;

				if (there.red_y < there.blue_y)
				{
					while (board[there.red_x][there.red_y - 1] == '.' || board[there.red_x][there.red_y - 1] == 'O')
					{
						there.red_y--;

						//출구를 만났을때
						if (board[there.red_x][there.red_y] == 'O')
							break;
					}

					while (board[there.blue_x][there.blue_y - 1] == '.' || board[there.blue_x][there.blue_y - 1] == 'O')
					{
						there.blue_y--;

						//출구를 만났을때
						if (board[there.blue_x][there.blue_y] == 'O')
							break;

						//먼저 움직인 구슬과 위치가 겹쳤을때
						if (there.red_x == there.blue_x && there.red_y == there.blue_y)
						{
							there.blue_y++;
							break;
						}
					}
				}

				else
				{
					while (board[there.blue_x][there.blue_y - 1] == '.' || board[there.blue_x][there.blue_y - 1] == 'O')
					{
						there.blue_y--;

						if (board[there.blue_x][there.blue_y] == 'O')
							break;
					}

					while (board[there.red_x][there.red_y - 1] == '.' || board[there.red_x][there.red_y - 1] == 'O')
					{
						there.red_y--;

						if (board[there.red_x][there.red_y] == 'O')
							break;

						if (there.red_x == there.blue_x && there.red_y == there.blue_y)
						{
							there.red_y++;
							break;
						}
					}
				}

			}


			if (i == 1) //위쪽으로 기울기
			{
				there = here;

				if (there.red_x < there.blue_x)
				{
					while (board[there.red_x - 1][there.red_y] == '.' || board[there.red_x - 1][there.red_y] == 'O')
					{
						there.red_x--;

						if (board[there.red_x][there.red_y] == 'O')
							break;
					}

					while (board[there.blue_x - 1][there.blue_y] == '.' || board[there.blue_x - 1][there.blue_y] == 'O')
					{
						there.blue_x--;

						if (board[there.blue_x][there.blue_y] == 'O')
							break;

						if (there.red_x == there.blue_x && there.red_y == there.blue_y)
						{
							there.blue_x++;
							break;
						}
					}
				}

				else
				{
					while (board[there.blue_x - 1][there.blue_y] == '.' || board[there.blue_x - 1][there.blue_y] == 'O')
					{
						there.blue_x--;

						if (board[there.blue_x][there.blue_y] == 'O')
							break;
					}

					while (board[there.red_x - 1][there.red_y] == '.' || board[there.red_x - 1][there.red_y] == 'O')
					{
						there.red_x--;

						if (board[there.red_x][there.red_y] == 'O')
							break;

						if (there.red_x == there.blue_x && there.red_y == there.blue_y)
						{
							there.red_x++;
							break;
						}
					}
				}
			}

			if (i == 2) //오른쪽으로 기울기
			{
				there = here;

				if (there.red_y > there.blue_y)
				{
					while (board[there.red_x][there.red_y + 1] == '.' || board[there.red_x][there.red_y + 1] == 'O')
					{
						there.red_y++;

						if (board[there.red_x][there.red_y] == 'O')
							break;
					}

					while (board[there.blue_x][there.blue_y + 1] == '.' || board[there.blue_x][there.blue_y + 1] == 'O')
					{
						there.blue_y++;

						if (board[there.blue_x][there.blue_y] == 'O')
							break;

						if (there.red_x == there.blue_x && there.red_y == there.blue_y)
						{
							there.blue_y--;
							break;
						}
					}
				}

				else
				{
					while (board[there.blue_x][there.blue_y + 1] == '.' || board[there.blue_x][there.blue_y + 1] == 'O')
					{
						there.blue_y++;

						if (board[there.blue_x][there.blue_y] == 'O')
							break;
					}

					while (board[there.red_x][there.red_y + 1] == '.' || board[there.red_x][there.red_y + 1] == 'O')
					{
						there.red_y++;

						if (board[there.red_x][there.red_y] == 'O')
							break;

						if (there.red_x == there.blue_x && there.red_y == there.blue_y)
						{
							there.red_y--;
							break;
						}
					}
				}

			}

			if (i == 3) //아래쪽으로 기울기
			{
				there = here;

				if (there.red_x > there.blue_x)
				{
					while (board[there.red_x + 1][there.red_y] == '.' || board[there.red_x + 1][there.red_y] == 'O')
					{
						there.red_x++;

						if (board[there.red_x][there.red_y] == 'O')
							break;
					}

					while (board[there.blue_x + 1][there.blue_y] == '.' || board[there.blue_x + 1][there.blue_y] == 'O')
					{
						there.blue_x++;

						if (board[there.blue_x][there.blue_y] == 'O')
							break;

						if (there.red_x == there.blue_x && there.red_y == there.blue_y)
						{
							there.blue_x--;
							break;
						}
					}
				}

				else
				{
					while (board[there.blue_x + 1][there.blue_y] == '.' || board[there.blue_x + 1][there.blue_y] == 'O')
					{
						there.blue_x++;

						if (board[there.blue_x][there.blue_y] == 'O')
							break;
					}

					while (board[there.red_x + 1][there.red_y] == '.' || board[there.red_x + 1][there.red_y] == 'O')
					{
						there.red_x++;

						if (board[there.red_x][there.red_y] == 'O')
							break;

						if (there.red_x == there.blue_x && there.red_y == there.blue_y)
						{
							there.red_x--;
							break;
						}
					}
				}
			}

			//기울여서 얻은 빨간구슬과 파란구슬의 위치가 발견된적이 없을때
			if (discoverd[there.red_x][there.red_y][there.blue_x][there.blue_y] == 0)
			{
				discoverd[there.red_x][there.red_y][there.blue_x][there.blue_y] = 1;
				depth[there.red_x][there.red_y][there.blue_x][there.blue_y] = depth[here.red_x][here.red_y][here.blue_x][here.blue_y] + 1;
				q.push(there);
			}

		}

	}

	return -1;
}

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

	string temp;
	Red_Blue red_blue_start;
	pair<int, int> exit;

	pre_discoverd();

	cin >> n >> m;

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

		for (int j = 0; j < m; j++)
		{
			//빨강구슬과 파란구슬의 위치를 알게 되면 위치를 저장하고
			//보드판에는 '.'으로 표시한다
			if (temp[j] == 'R')
			{
				red_blue_start.red_x = i;
				red_blue_start.red_y = j;
				temp[j] = '.';
			}
			else if (temp[j] == 'B')
			{
				red_blue_start.blue_x = i;
				red_blue_start.blue_y = j;
				temp[j] = '.';
			}

			//출구의 위치를 저장한다
			else if (temp[j] == 'O')
				exit = make_pair(i, j);
		}

		board.push_back(temp);
	}

	cout << Solve(red_blue_start, exit);

	return 0;
}
저작자표시

'알고리즘 문제풀이' 카테고리의 다른 글

[백준/BOJ] 백준 1922번 : 네트워크 연결  (0) 2020.08.13
[백준/BOJ] 백준 1197번 : 최소 스패닝 트리  (0) 2020.08.13
[백준/BOJ] 백준 2644번 : 촌수계산  (0) 2020.08.13
[백준/BOJ] 백준 2146번 : 다리 만들기  (0) 2020.08.12
[백준/BOJ] 백준 1389번 : 케빈 베이컨의 6단계 법칙  (0) 2020.08.12

관련글

댓글 0

티스토리툴바