[BOJ / 삼성A형기출] 13460 구술 탈출 2

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

13460번: 구슬 탈출 2

 

13460 구술탈출 2

알고리즘 : BFS

완전탐색문제이며 탈출구가 트리의 끝이 아닌 중간에 있을 가능성이 존재하고 지금까지 구한 최솟값보다 더 큰 이동의 경우를 백트래킹 하기 위해서 DFS보다 BFS가 훨씬 빠르다고 볼 수 있습니다.

10번의 이하의 행동으로 탈출을 시켜야 하므로 9번이하인 애들만 큐에서 작동하여야 합니다.

 

방향에 따라 어떤 공을 먼저 움직일 지를 정해주어야 하는데 만약 빨간공이 3,3 파란공이 3,4에 있다고 하고

오른쪽으로 슬라이드를 한다고 한다면 x값이 증가하는 방향이므로 x값이 더 큰 파란공을 먼저 움직여 주어야 문제가 없습니다.

이 부분과 공이 빠졌을 때만 처리해주면 풀이 가능합니다.

 

 

 

 

< CODE >

#include <iostream>
#include <queue>
#include <climits>

using namespace std;

#define MAX 13

int n, m;
char map[MAX][MAX];
int ry, rx, by, bx;
int smallArrive = 11;

//상좌하우
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,-1,0,1 };

struct Q
{
	int ry;
	int rx;
	int by;
	int bx;
	int move;
};

queue<Q> q;

// 영역검사
bool Safe(int y, int x)
{
	if (y >= 0 && x >= 0 && y < n && x < m && map[y][x] != '#')
		return true;
	return false;
}

// 메인코드
Q move(Q now, int dir)
{
	Q first = now;
	bool redFirst = false;

	switch (dir)
	{
	case 0:
		//상
		redFirst = now.ry <= now.by;
		break;
	case 1:
		//좌
		redFirst = now.rx <= now.bx;
		break;
	case 2:
		//하
		redFirst = now.ry > now.by;
		break;
	case 3:
		//우
		redFirst = now.rx > now.bx;
		break;
	}

	//빨강과 파랑공이 들어갔는지 확인하는 변수
	bool redIn = false;
	bool blueIn = false;

	while (true)
	{
		// 두 공 모두 움직이지 못할 경우 한 번의 슬라이드 끝
		bool move = false;

		if (redFirst)
		{
			if (!redIn && Safe(now.ry + dy[dir], now.rx + dx[dir]))
			{
				now.ry = now.ry + dy[dir];
				now.rx = now.rx + dx[dir];

				move = true;

				if (map[now.ry][now.rx] == 'O')
					redIn = true;
			}

			if (!blueIn && Safe(now.by + dy[dir], now.bx + dx[dir]))
			{
				if (map[now.by + dy[dir]][now.bx + dx[dir]] == 'O')
				{
					now.by = now.by + dy[dir];
					now.bx = now.bx + dx[dir];
					blueIn = true;
					move = true;
				}
				else if (!(now.by + dy[dir] == now.ry && now.bx + dx[dir] == now.rx))
				{
					now.by = now.by + dy[dir];
					now.bx = now.bx + dx[dir];
					move = true;
				}
			}
		}
		else
		{
			if (!blueIn && Safe(now.by + dy[dir], now.bx + dx[dir]))
			{
				now.by = now.by + dy[dir];
				now.bx = now.bx + dx[dir];

				move = true;

				if (map[now.by][now.bx] == 'O')
					blueIn = true;
			}

			if (!redIn && Safe(now.ry + dy[dir], now.rx + dx[dir]))
			{
				if (map[now.ry + dy[dir]][now.rx + dx[dir]] == 'O')
				{
					now.ry = now.ry + dy[dir];
					now.rx = now.rx + dx[dir];
					redIn = true;
					move = true;
				}
				else if (!(now.ry + dy[dir] == now.by && now.rx + dx[dir] == now.bx))
				{
					now.ry = now.ry + dy[dir];
					now.rx = now.rx + dx[dir];
					move = true;
				}
			}
		}

		if (!move)
			break;
	}

	// move를 -1이 될 경우 큐에 넣지 않음
	if (now.ry == first.ry && now.rx == first.rx && now.by == first.by && now.bx == first.bx || blueIn)
		now.move = -1;
	else
		now.move += 1;

	if (redIn && !blueIn)
	{
		if(now.move < smallArrive)
			smallArrive = now.move;
		now.move = -1;
	}

	return now;

}

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

	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')
			{
				ry = i;
				rx = j;
			}

			if (map[i][j] == 'B')
			{
				by = i;
				bx = j;
			}
		}
	}

	q.push({ ry, rx, by, bx, 0 });

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

		if (here.move >= smallArrive && here.move > 9)
			continue;

		// direction
		for (int i = 0; i < 4; i++)
		{
			Q temp = move(here, i);

			if (temp.move != -1)
				q.push(temp);
		}
	}

	if (smallArrive == 11)
		cout << "-1\n";
	else
		cout << smallArrive << '\n';

	return 0;
}

8ms로 통과하였습니다.

 

 

 

 

#구슬탈출2 #BOJ 13460 #BOJ #13460 #삼성A형기출