백준 13460번: 구슬 탈출 2

[문제 링크]

13460번: 구슬 탈출 2

---

너비 우선 탐색을 공부하기 전에 한번 풀어봤던 문제였다. 그때는 몇시간을 고민해도 결국 시간초과의 늪에서 빠져나오지 못했었는데 너비 우선 탐색으로 접근하니까 어렵지 않게 풀 수 있었다.

 

입력받는 단계에서 R, B, O 의 위치를 미리 저장한 다음, R의 위치와 B의 위치를 queue에 담고 너비 우선 탐색을 시작한다.

기울였을 때 앞에 있는 볼보다 뒤에 있는 볼이 먼저 움직이는 상황을 방지하기 위해 기울이는 방향에 따라 더 앞에 있는 볼 먼저 움직이도록 구현하였다.

---

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

struct Pos {
	int y;
	int x;

	bool operator== (const Pos& rhs)
	{
		if (y == rhs.y && x == rhs.x) 
			return true;
		else 
			return false;
	}
};

Pos R, B, O;
char board[10][10];
int N, M;
int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };

void Move_R(Pos& thereR, const Pos& thereB, int type)
{
	while (1) {
		Pos next = { thereR.y + dy[type], thereR.x + dx[type] };

		if (board[next.y][next.x] == '#') break;
		if (board[next.y][next.x] == 'O') {
			thereR = next;
			break;
		}
		else if (next == thereB) {
			break;
		}
		else {
			thereR = next;
		}
	}
}

void Move_B(const Pos& thereR, Pos& thereB, int type)
{
	while (1) {
		Pos next = { thereB.y + dy[type], thereB.x + dx[type] };

		if (board[next.y][next.x] == '#') break;
		if (board[next.y][next.x] == 'O') {
			thereB = next;
			break;
		}
		else if (next == thereR) {
			break;
		}
		else {
			thereB = next;
		}
	}
}

void MovingBall(Pos& thereR, Pos& thereB, int type)
{
	if (type == 0) { // 좌로 이동
		// 이동 방향 기준으로 R이 앞에 있는 경우
		if (thereR.y == thereB.y && thereR.x > thereB.x) {
			// R 먼저
			Move_R(thereR, thereB, type);
			Move_B(thereR, thereB, type);
		}
		else {
			// B 먼저
			Move_B(thereR, thereB, type);
			Move_R(thereR, thereB, type);
		}
	}

	else if (type == 1) { // 우로 이동
		// 이동 방향 기준으로 R이 앞에 있는 경우
		if (thereR.y == thereB.y && thereR.x < thereB.x) {
			// R 먼저
			Move_R(thereR, thereB, type);
			Move_B(thereR, thereB, type);
		}
		else {
			// B 먼저
			Move_B(thereR, thereB, type);
			Move_R(thereR, thereB, type);
		}
	}

	else if (type == 2) { // 아래로 이동
		// 이동 방향 기준으로 R이 앞에 있는 경우
		if (thereR.x == thereB.x && thereR.y > thereB.y) {
			// R 먼저
			Move_R(thereR, thereB, type);
			Move_B(thereR, thereB, type);
		}
		else {
			// B 먼저
			Move_B(thereR, thereB, type);
			Move_R(thereR, thereB, type);
		}
	}


	else if (type == 3) { // 위로 이동
		// 이동 방향 기준으로 R이 앞에 있는 경우
		if (thereR.x == thereB.x && thereR.y < thereB.y) {
			// R 먼저
			Move_R(thereR, thereB, type);
			Move_B(thereR, thereB, type);
		}
		else {
			// B 먼저
			Move_B(thereR, thereB, type);
			Move_R(thereR, thereB, type);
		}
	}
}

int bfs()
{
	queue<pair<pair<Pos, Pos>, int>> q;
	q.push({ { R, B }, 0 });

	while (!q.empty())
	{
		Pos hereR = q.front().first.first;
		Pos hereB = q.front().first.second;
		int move = q.front().second;

		q.pop();

		// 이동횟수 10회 초과 시 불가능
		if (move > 10) break;

		// R or B 가 구멍에 들어갔을 경우
		if (O == hereR || O == hereB)
		{
			if (O == hereB) // B가 구멍에 빠지면 실패 
				continue;
			else			// R만 구멍에 빠지면 성공
				return move;
		}

		for (int i = 0; i < 4; i++)
		{
			Pos thereR = hereR;
			Pos thereB = hereB;
			MovingBall(thereR, thereB, i);
			
			// 두 공다 움직이지 않았다면 건너뜀
			if (thereR == hereR && thereB == hereB) continue;

			q.push({ {thereR, thereB}, move + 1 });
		}
	}

	return -1;
}

int main(void)
{
	cin >> N >> M;

	for(int i=0; i<N; i++)
		for (int j = 0; j < M; j++)
		{
			cin >> board[i][j];

			if (board[i][j] == 'R')
				R = { i,j };
			else if (board[i][j] == 'B')
				B = { i,j };
			else if (board[i][j] == 'O')
				O = { i,j };
		}

	cout << bfs() << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 163 day