백준 - 구슬 탈출 2 (13460) [C++]

 이 문제는 시뮬레이션 문제로, 구현이 매우 어려운 문제였다. 중간에 풀다가 안 풀려서 구글링을 했지만 bfs를 이용한 풀이가 많았고, 이는 내가 처음에 구현한 것과 접근 방식이 너무 달라 적용하지 못했다. 결국 다시 반례들을 적용하면서 천천히 디버깅했고, 문제를 발견하여 해결할 수 있었다. 

 

 내 풀이의 핵심은 RED를 먼저 굴리고, BLUE를 그 다음, RED 한번 더, BLUE 한번 더 이다. 여기서 시간 초과가 나지 않으려면 위 과정을 거쳐도 두 구슬 모두 제자리에 있으면 바로 continue를 해버리는 것이다. 그렇지 않으면 가만히 있는 모든 케이스를 탐색하므로 시간 초과가 발생한다.

 

 내가 놓쳤던 부분은 첫번째로 RED와 BLUE를 탐색하고, 한번 더 탐색하는 부분이었는데, 이 때 매개변수로 받은 red를 써서 첫번째로 일부 구른 부분이 반영이 안된 것이었다. 예를 들어 구슬이 BLUE RED 이런식으로 있고 LEFT로 굴린다고 치면 RED 먼저 굴릴 시 BLUE가 있으므로 안 구르게 되어 한번더 해주면 제대로 작동한다. 하지만 첫번째에서 아예 안 움직이는게 아닌 일부만 움직일 경우에는 반영되지 않는다. 따라서 첫번째 구슬 이동으로 나온 결과를 바탕으로 두번째 구슬 이동을 해야 제대로 작동한다.

 

 

 

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;

#define BLANK '.'
#define WALL '#'
#define HOLE 'O'
#define RED 'R'
#define BLUE 'B'

#define LEFT 1
#define UP 2
#define RIGHT 3
#define DOWN 4

#define MAX 10000

pair<int, int> nextPos(vector<vector<char>>& board, int y, int x, int direction)
{
	if (board[y][x] == HOLE)
	{
		return { y, x };
	}

	switch (direction)
	{
	case LEFT:
		while (true)
		{
			if (board[y][x - 1] == BLANK)
			{
				x--;
			}
			else if (board[y][x - 1] == HOLE)
			{
				x--;
				break;
			}
			else
			{
				break;
			}
		}

		break;
	case UP:
		while (true)
		{
			if (board[y - 1][x] == BLANK)
			{
				y--;
			}
			else if (board[y - 1][x] == HOLE)
			{
				y--;
				break;
			}
			else
			{
				break;
			}
		}

		break;
	case RIGHT:
		while (true)
		{
			if (board[y][x + 1] == BLANK)
			{
				x++;
			}
			else if (board[y][x + 1] == HOLE)
			{
				x++;
				break;
			}
			else
			{
				break;
			}
		}

		break;
	case DOWN:
		while (true)
		{
			if (board[y + 1][x] == BLANK)
			{
				y++;
			}
			else if (board[y + 1][x] == HOLE)
			{
				y++;
				break;
			}
			else
			{
				break;
			}
		}

		break;
	}

	return { y, x };
}

int solution(vector<vector<char>> board, int stage, pair<int, int> red, pair<int, int> blue)
{
	if (stage > 10)
	{
		return MAX;
	}

	int answer = MAX;
	for (int direction = 1; direction <= 4; direction++)
	{
		vector<vector<char>> tempBoard = board;
		pair<int, int> redNext = red;
		pair<int, int> blueNext = blue;

		bool redHole = false;
		bool blueHole = false;
		bool redMove = false;
		bool blueMove = false;

		// 1. red move
		redNext = nextPos(tempBoard, red.first, red.second, direction);

		if (redNext != red)
		{
			if (tempBoard[redNext.first][redNext.second] == HOLE)
			{
				redHole = true;
				redMove = true;
				tempBoard[red.first][red.second] = BLANK;
			}
			else
			{
				redMove = true;
				tempBoard[red.first][red.second] = BLANK;
				tempBoard[redNext.first][redNext.second] = RED;
			}
		}

		// 2. blue move
		blueNext = nextPos(tempBoard, blue.first, blue.second, direction);

		if (blueNext != blue)
		{
			if (tempBoard[blueNext.first][blueNext.second] == HOLE)
			{
				blueHole = true;
				blueMove = true;
				tempBoard[blue.first][blue.second] = BLANK;
			}
			else
			{
				blueMove = true;
				tempBoard[blue.first][blue.second] = BLANK;
				tempBoard[blueNext.first][blueNext.second] = BLUE;
			}
		}

		// 3. if red no move, red move again
		pair<int, int> tempRed = redNext;
		redNext = nextPos(tempBoard, tempRed.first, tempRed.second, direction);
		
		if (redNext != tempRed)
		{
			if (tempBoard[redNext.first][redNext.second] == HOLE)
			{
				redHole = true;
				redMove = true;
				tempBoard[tempRed.first][tempRed.second] = BLANK;
			}
			else
			{
				redMove = true;
				tempBoard[tempRed.first][tempRed.second] = BLANK;
				tempBoard[redNext.first][redNext.second] = RED;
			}
		}
		

		// 4. if blue no move, blue move again
		pair<int, int> tempBlue = blueNext;
		blueNext = nextPos(tempBoard, tempBlue.first, tempBlue.second, direction);

		if (blueNext != blue)
		{
			if (tempBoard[blueNext.first][blueNext.second] == HOLE)
			{
				blueHole = true;
				blueMove = true;
				tempBoard[tempBlue.first][tempBlue.second] = BLANK;
			}
			else
			{
				blueMove = true;
				tempBoard[tempBlue.first][tempBlue.second] = BLANK;
				tempBoard[blueNext.first][blueNext.second] = BLUE;
			}
		}
		

		if (!redMove && !blueMove)
		{
			continue;
		}

		// check hole
		if (redHole && !blueHole)
		{
			// success
			return stage;
		}
		else if ((redHole && blueHole) || (!redHole && blueHole))
		{
			// fail
			continue;
		}
		else if (!redHole && !blueHole)
		{
			// continue
			answer = min(answer, solution(tempBoard, stage + 1, redNext, blueNext));
		}
	}

	return answer;
}


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

	cin >> N >> M;

	vector<vector<char>> board(N, vector<char>(M));

	pair<int, int> red, blue;

	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < M; x++)
		{
			char temp;

			cin >> temp;

			board[y][x] = temp;

			if (temp == RED)
			{
				red = { y, x };
			}
			if (temp == BLUE)
			{
				blue = { y,x };
			}
		}
	}

	int answer = solution(board, 1, red, blue);

	if (answer == MAX)
	{
		cout << -1 << '\n';
	}
	else
	{
		cout << answer << '\n';
	}

	return 0;
}

 

 

 

// 수정 - 2024-04-08

약 8개월만에 다시 풀어봤다.

 

이 문제는 BFS로 푸는 것이 좀 더 직관적이다. 

또한 계속 board를 갱신하며 'R'과 'B' 위치를 바꾸는 방식이 아닌, 위치를 따로 저장해놓고 해당 공들의 위치로 상태를 저장하는 것이 좀 더 구현하기 편하다.

 

두 공 중 어떤 것을 먼저 굴릴지가 중요한데, 각 방향에 대해서 좀 더 앞에 있는 공을 먼저 굴리는 방식을 선택했다. 하나의 공을 굴리는 함수를 정의하면 단순히 각 공에 대한 위치만 던져주면 똑같은 로직으로 작동하기 때문이다.

 

한번 풀어 본 문제라 그런지 30분만에 풀 수 있었다. 

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

#define INF 1000000000
#define HOLE 'O'
#define WALL '#'
#define EMPTY '.'
#define RED 'R'
#define BLUE 'B'
#define LEFT 0
#define RIGHT 1
#define UP 2
#define DOWN 3

struct Ball {
	int redY;
	int redX;
	int blueY;
	int blueX;
};

int N, M;
vector<vector<char>> board;
Ball init;

void input() {
	cin >> N >> M;
	board = vector<vector<char>>(N, vector<char>(M));
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> board[y][x];
			
			if (board[y][x] == RED) {
				board[y][x] = EMPTY;
				init.redY = y;
				init.redX = x;
			} else if (board[y][x] == BLUE) {
				board[y][x] = EMPTY;
				init.blueY = y;
				init.blueX = x;
			}
		}
	}
}

pair<int, int> nextPos(int y, int x, int direction) {
	switch (direction) {
	case LEFT:
		x--;
		break;
	case RIGHT:
		x++;
		break;
	case UP:
		y--;
		break;
	case DOWN:
		y++;
		break;
	}
	return { y, x };
}

pair<int, int> moveOneBall(int y, int x, int direction, pair<int, int> oppo) {
	pair<int, int> present = { y, x };
	while (true) {
		pair<int, int> next = nextPos(present.first, present.second, direction);

		char state = board[next.first][next.second];

		if (state == '#') {
			return present;
		}

		if (state == 'O') {
			return { -1, -1 };
		}

		if (next.first == oppo.first && next.second == oppo.second) {
			return present;
		}

		present = next;
	}
}

Ball move(Ball ball, int direction) {
	switch (direction) {
	case LEFT:
		if (ball.redX <= ball.blueX) {
			pair<int, int> red = moveOneBall(ball.redY, ball.redX, direction, {ball.blueY, ball.blueX});
			pair<int, int> blue = moveOneBall(ball.blueY, ball.blueX, direction, red);
			return { red.first, red.second, blue.first, blue.second };
		} else {
			pair<int, int> blue = moveOneBall(ball.blueY, ball.blueX, direction, { ball.redY, ball.redX });
			pair<int, int> red = moveOneBall(ball.redY, ball.redX, direction, blue);
			return { red.first, red.second, blue.first, blue.second };
		}
		break;
	case RIGHT:
		if (ball.redX >= ball.blueX) {
			pair<int, int> red = moveOneBall(ball.redY, ball.redX, direction, { ball.blueY, ball.blueX });
			pair<int, int> blue = moveOneBall(ball.blueY, ball.blueX, direction, red);
			return { red.first, red.second, blue.first, blue.second };
		} else {
			pair<int, int> blue = moveOneBall(ball.blueY, ball.blueX, direction, { ball.redY, ball.redX });
			pair<int, int> red = moveOneBall(ball.redY, ball.redX, direction, blue);
			return { red.first, red.second, blue.first, blue.second };
		}
		break;
	case UP:
		if (ball.redY <= ball.blueY) {
			pair<int, int> red = moveOneBall(ball.redY, ball.redX, direction, { ball.blueY, ball.blueX });
			pair<int, int> blue = moveOneBall(ball.blueY, ball.blueX, direction, red);
			return { red.first, red.second, blue.first, blue.second };
		} else {
			pair<int, int> blue = moveOneBall(ball.blueY, ball.blueX, direction, { ball.redY, ball.redX });
			pair<int, int> red = moveOneBall(ball.redY, ball.redX, direction, blue);
			return { red.first, red.second, blue.first, blue.second };
		}
		break;
	case DOWN:
		if (ball.redY >= ball.blueY) {
			pair<int, int> red = moveOneBall(ball.redY, ball.redX, direction, { ball.blueY, ball.blueX });
			pair<int, int> blue = moveOneBall(ball.blueY, ball.blueX, direction, red);
			return { red.first, red.second, blue.first, blue.second };
		} else {
			pair<int, int> blue = moveOneBall(ball.blueY, ball.blueX, direction, { ball.redY, ball.redX });
			pair<int, int> red = moveOneBall(ball.redY, ball.redX, direction, blue);
			return { red.first, red.second, blue.first, blue.second };
		}
		break;
	}

	return { -1, -1, -1, -1 };
}

int func(Ball ball) {
	queue<pair<Ball, int>> q;
	
	q.push({ ball, 0 });

	while (!q.empty()) {
		Ball presentBall = q.front().first;
		int presentCnt = q.front().second;
		q.pop();

		if (presentCnt == 10) {
			continue;
		}

		for (int i = 0; i < 4; i++) {
			Ball next = move(presentBall, i);
			
			if (next.blueY == -1) {
				continue;
			}

			if (next.redY == -1) {
				return presentCnt + 1;
			}

			q.push({ next, presentCnt + 1 });
		}
	}

	return -1;
}

int solve() {
	int result = func(init);

	return result;
}

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

	input();
	cout << solve() << '\n';

	return 0;
}