알고리즘/Baekjoon

[C++] 백준 13460번 구슬 탈출 2

kimyunseok 2022. 9. 2. 19:05
 

13460번: 구슬 탈출 2

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

www.acmicpc.net

삼성 SW 역량 테스트 기출 문제 수록 문제.

구현 / 시뮬레이션 문제로, 설계를 잘하고 구현을 해야 풀 수 있는 문제.

 

문제 분석

문제의 조건은 다음과 같다.

  • N*M 보드가 있고, 보드에는 구멍이 하나 있다.
  • 빨간 구슬과 파란 구슬이 있다.
  • 빨간 구슬을 구멍으로 빼야 한다.
  • 파란 구슬은 구멍으로 빠지면 안된다.
  • 구슬은 직접 움직일 수 없고 보드를 상, 하, 좌, 우로 기울여서 움직여야 한다.
    -> 이 때, 두 개의 구슬이 동시에 움직인다.
  • 한 칸에는 한 개의 구슬만 있을 수 있다.

문제에서 요구하는 정답은, 최소 몇 번만에 빨간 구슬'만'을 빼낼 수 있는 지 찾아야 하며,

10번 이내로 구해야 한다.

 

공은 보드를 기울여서 움직여야 하므로, 한 번 움직일 때, 해당 방향으로 최대로 움직이게 된다.

움직일 때 고려해야 할 점은 다음과 같다.

  1. 어떤 구슬이 먼저 움직이게 될까?

  2. 파란 구슬이 구멍에 도달했는가? -> 맞다면 고려 대상에서 제외.

  3. 두 구슬이 움직인 곳이, 이미 예전에 방문했던 상황인가? -> 맞다면 고려 대상에서 제외.

  4. 빨간 구슬'만' 구멍에 도달했는가? -> 종료되는 조건.

  5. 두 구슬 모두 구멍에 도달하지 않았다면, 해당 좌표에서 다시 기울이는 작업을 해 주어야 한다.

 

1번의 고려해야 할 점은 다음과 같이 해결할 수 있다.

구슬의 좌표를 (r, c)라고 할 때,

  1. 기울이는 방향이 위쪽일 경우 : 두 구슬 중, r이 작은 게 먼저 움직인다.

  2. 기울이는 방향이 오른쪽일 경우 : 두 구슬 중, c가 큰 게 먼저 움직인다.
  3. 기울이는 방향이 아래쪽일 경우 : 두 구슬 중, r이 큰 게 먼저 움직인다.

  4. 기울이는 방향이 왼쪽일 경우 : 두 구슬 중, c가 작은 게 먼저 움직인다.

처음에 빨간 구슬 먼저 이동하게 구현했다가, 해당 조건을 추가로 고려하게 됐다.

 

구현

/*
* 백준 13460번 구슬 탈출 2
* https://www.acmicpc.net/problem/13460
* 구현 / 시뮬레이션 / 그래프 탐색
*/

#include <iostream>
#include <queue>

using namespace std;

struct Point {
	int r;
	int c;
};

queue<pair<Point, Point>> ballPointQ[12];
int height, width;
Point redBall, blueBall, holePoint;
Point redBallPointForCheck;
Point blueBallPointForCheck;
char maze[11][11];
bool visit[11][11][11][11];
bool redBallInHole, blueBallInHole;
int result = -1;
Point directions[4] = {
	{-1, 0},
	{0, 1},
	{1, 0},
	{0, -1}
};

void moveRedBallFirst(Point direction, int idx) {

	while (maze[redBallPointForCheck.r + direction.r][redBallPointForCheck.c + direction.c] != '#' &&
		!(redBallPointForCheck.r + direction.r == blueBallPointForCheck.r && redBallPointForCheck.c + direction.c == blueBallPointForCheck.c)
		) {
		redBallPointForCheck.r += direction.r;
		redBallPointForCheck.c += direction.c;

		if (maze[redBallPointForCheck.r][redBallPointForCheck.c] == 'O') {
			redBallPointForCheck.r = -1;
			redBallPointForCheck.c = -1;
			redBallInHole = true;
			break;
		}
	}

	while (maze[blueBallPointForCheck.r + direction.r][blueBallPointForCheck.c + direction.c] != '#' &&
		!(redBallPointForCheck.r == blueBallPointForCheck.r + direction.r && redBallPointForCheck.c == blueBallPointForCheck.c + direction.c)
		) {
		blueBallPointForCheck.r += direction.r;
		blueBallPointForCheck.c += direction.c;

		if (maze[blueBallPointForCheck.r][blueBallPointForCheck.c] == 'O') {
			blueBallInHole = true;
			break;
		}
	}

}

void moveBlueBallFirst(Point direction, int idx) {

	while (maze[blueBallPointForCheck.r + direction.r][blueBallPointForCheck.c + direction.c] != '#' &&
		!(redBallPointForCheck.r == blueBallPointForCheck.r + direction.r && redBallPointForCheck.c == blueBallPointForCheck.c + direction.c)
		) {
		blueBallPointForCheck.r += direction.r;
		blueBallPointForCheck.c += direction.c;

		if (maze[blueBallPointForCheck.r][blueBallPointForCheck.c] == 'O') {
			blueBallPointForCheck.r = -1;
			blueBallPointForCheck.c = -1;
			blueBallInHole = true;
			break;
		}
	}

	while (maze[redBallPointForCheck.r + direction.r][redBallPointForCheck.c + direction.c] != '#' &&
		!(redBallPointForCheck.r + direction.r == blueBallPointForCheck.r && redBallPointForCheck.c + direction.c == blueBallPointForCheck.c)
		) {
		redBallPointForCheck.r += direction.r;
		redBallPointForCheck.c += direction.c;

		if (maze[redBallPointForCheck.r][redBallPointForCheck.c] == 'O') {
			redBallInHole = true;
			break;
		}
	}
}

void moveBall(int idx) {

	while (!ballPointQ[idx].empty()) {
		Point redBallPoint = ballPointQ[idx].front().first;
		Point blueBallPoint = ballPointQ[idx].front().second;

		//cout << idx << "\n";
		//cout << "red : " << redBallPoint.r << ", " << redBallPoint.c << "\n";
		//cout << "blue : " << blueBallPoint.r << ", " << blueBallPoint.c << "\n\n";

		ballPointQ[idx].pop();

		for (int i = 0; i < 4; i++) {
			Point direction = directions[i];
			redBallInHole = false;
			blueBallInHole = false;

			redBallPointForCheck = redBallPoint;
			blueBallPointForCheck = blueBallPoint;

			if (i == 0) {
				if (redBallPointForCheck.r < blueBallPointForCheck.r) {
					moveRedBallFirst(direction, idx);
				}
				else {
					moveBlueBallFirst(direction, idx);
				}
			}
			else if (i == 1) {
				if (redBallPointForCheck.c > blueBallPointForCheck.c) {
					moveRedBallFirst(direction, idx);
				}
				else {
					moveBlueBallFirst(direction, idx);
				}
			}
			else if (i == 2) {
				if (redBallPointForCheck.r > blueBallPointForCheck.r) {
					moveRedBallFirst(direction, idx);
				}
				else {
					moveBlueBallFirst(direction, idx);
				}
			}
			else {
				if (redBallPointForCheck.c < blueBallPointForCheck.c) {
					moveRedBallFirst(direction, idx);
				}
				else {
					moveBlueBallFirst(direction, idx);
				}
			}

			if (redBallInHole && !blueBallInHole) {
				return;
			}
			else if (!blueBallInHole &&
				!visit[redBallPointForCheck.r][redBallPointForCheck.c][blueBallPointForCheck.r][blueBallPointForCheck.c]) {

				visit[redBallPointForCheck.r][redBallPointForCheck.c][blueBallPointForCheck.r][blueBallPointForCheck.c] = true;
				ballPointQ[idx + 1].push({ redBallPointForCheck, blueBallPointForCheck });
			}
		}

	}

}

void go(int idx) {
	if (idx > 10) { return; }

	moveBall(idx);

	if (redBallInHole && !blueBallInHole) {
		result = idx;
		return;
	}
	else {
		go(idx + 1);
	}
}

int main() {
	cin >> height >> width;

	for (int r = 1; r <= height; r++) {
		for (int c = 1; c <= width; c++) {
			cin >> maze[r][c];
			if (maze[r][c] == 'R') {
				redBall.r = r;
				redBall.c = c;
			}
			else if (maze[r][c] == 'B') {
				blueBall.r = r;
				blueBall.c = c;
			}
			else if (maze[r][c] == 'O') {
				holePoint.r = r;
				holePoint.c = c;
			}
		}
	}

	visit[redBall.r][redBall.c][blueBall.r][blueBall.c] = true;
	ballPointQ[1].push({ redBall, blueBall });

	go(1);

	cout << result;

	return 0;
}

 

변수

  • Point 구조체 : 좌표를 r과 c로 나타내기 위한 구조체
  • ballPointQ 큐 : 1 ~ 10번째까지 고려해야 할 빨간 구슬과 파란 구슬의 좌표를 담고 있는 큐.
  • redBall, blueBall, holePoint : 최초의 빨간 공과 파란 공과 구멍의 좌표를 담고 있음.
  • redBallPointForCheck / blueBallPointForCheck : 빨간공과 파란공의 좌표를 체크하기 위한 변수
  • maze 배열 : 최초로 입력받는 보드의 정보
  • visit 배열 : [빨간공r행][빨간공c열][파란공r행][파란공c열]을 방문했는 지 체크하기 위한 배열
  • redBallInHole / blueBallInHole : 빨간 공과 파란 공이 이동하면서 구멍에 들어갔는 지 여부를 확인하기 위한 배열
  • result : 결과로 출력할 값
  • directions : 상,우,하,좌 방향을 담는 배열

 

메인함수

int main() {
	cin >> height >> width;

	for (int r = 1; r <= height; r++) {
		for (int c = 1; c <= width; c++) {
			cin >> maze[r][c];
			if (maze[r][c] == 'R') {
				redBall.r = r;
				redBall.c = c;
			}
			else if (maze[r][c] == 'B') {
				blueBall.r = r;
				blueBall.c = c;
			}
			else if (maze[r][c] == 'O') {
				holePoint.r = r;
				holePoint.c = c;
			}
		}
	}

	visit[redBall.r][redBall.c][blueBall.r][blueBall.c] = true;
	ballPointQ[1].push({ redBall, blueBall });

	go(1);

	cout << result;

	return 0;
}

문제의 조건을 입력받고, 최초의 빨간 구슬과 파란 구슬, 구멍의 좌표를 입력받는다.

시작 빨간 구슬과 파란 구슬의 좌표를 방문처리 한 후 첫 번째 idx로 큐에 넣어준다.

후에 문제의 조건을 찾는 go({idx번째}) 메서드를 실행한 후

result를 출력해준다.

 

문제의 조건을 찾는 go 메서드

void go(int idx) {
	if (idx > 10) { return; }

	moveBall(idx);

	if (redBallInHole && !blueBallInHole) {
		result = idx;
		return;
	}
	else {
		go(idx + 1);
	}
}

만일 현재 번째 수가 10번째가 넘었다면 return한다.

그게 아니라면 보드를 기울이는 moveBall({idx번째}) 메서드를 실행한다.

 

보드를 기울인 후, 빨간 공만 구멍에 들어갔다면 result 변수에 idx를 저장한 후 return한다.

아니라면, 다음 번째 수에서 찾아본다.

 

보드를 기울이는 moveBall 메서드

void moveBall(int idx) {

	while (!ballPointQ[idx].empty()) {
		Point redBallPoint = ballPointQ[idx].front().first;
		Point blueBallPoint = ballPointQ[idx].front().second;

		//cout << idx << "\n";
		//cout << "red : " << redBallPoint.r << ", " << redBallPoint.c << "\n";
		//cout << "blue : " << blueBallPoint.r << ", " << blueBallPoint.c << "\n\n";

		ballPointQ[idx].pop();

		for (int i = 0; i < 4; i++) {
			Point direction = directions[i];
			redBallInHole = false;
			blueBallInHole = false;

			redBallPointForCheck = redBallPoint;
			blueBallPointForCheck = blueBallPoint;

			if (i == 0) {
				if (redBallPointForCheck.r < blueBallPointForCheck.r) {
					moveRedBallFirst(direction, idx);
				}
				else {
					moveBlueBallFirst(direction, idx);
				}
			}
			else if (i == 1) {
				if (redBallPointForCheck.c > blueBallPointForCheck.c) {
					moveRedBallFirst(direction, idx);
				}
				else {
					moveBlueBallFirst(direction, idx);
				}
			}
			else if (i == 2) {
				if (redBallPointForCheck.r > blueBallPointForCheck.r) {
					moveRedBallFirst(direction, idx);
				}
				else {
					moveBlueBallFirst(direction, idx);
				}
			}
			else {
				if (redBallPointForCheck.c < blueBallPointForCheck.c) {
					moveRedBallFirst(direction, idx);
				}
				else {
					moveBlueBallFirst(direction, idx);
				}
			}

			if (redBallInHole && !blueBallInHole) {
				return;
			}
			else if (!blueBallInHole &&
				!visit[redBallPointForCheck.r][redBallPointForCheck.c][blueBallPointForCheck.r][blueBallPointForCheck.c]) {

				visit[redBallPointForCheck.r][redBallPointForCheck.c][blueBallPointForCheck.r][blueBallPointForCheck.c] = true;
				ballPointQ[idx + 1].push({ redBallPointForCheck, blueBallPointForCheck });
			}
		}

	}

}

현재 번째에서 고려해야할 좌표들에 대해 각각 상, 우, 하, 좌로 기울여본다.

기울일 때, 어떤 구슬이 먼저 움직이는 지는 위의 조건에서 설명했으므로 생략하겠다.

기울인 후에 빨간공만 구멍에 넣어졌다면, return으로 메서드를 종료한다.

그게 아니라면, 파란 공이 구멍에 없고 현재 각 구슬의 좌표가 방문하지 않았다면

방문 처리 후 다음 번째 큐에 넣어준다.

 

각 색깔의 구슬을 움직이는 메서드

void moveRedBallFirst(Point direction, int idx) {

	while (maze[redBallPointForCheck.r + direction.r][redBallPointForCheck.c + direction.c] != '#' &&
		!(redBallPointForCheck.r + direction.r == blueBallPointForCheck.r && redBallPointForCheck.c + direction.c == blueBallPointForCheck.c)
		) {
		redBallPointForCheck.r += direction.r;
		redBallPointForCheck.c += direction.c;

		if (maze[redBallPointForCheck.r][redBallPointForCheck.c] == 'O') {
			redBallPointForCheck.r = -1;
			redBallPointForCheck.c = -1;
			redBallInHole = true;
			break;
		}
	}

	while (maze[blueBallPointForCheck.r + direction.r][blueBallPointForCheck.c + direction.c] != '#' &&
		!(redBallPointForCheck.r == blueBallPointForCheck.r + direction.r && redBallPointForCheck.c == blueBallPointForCheck.c + direction.c)
		) {
		blueBallPointForCheck.r += direction.r;
		blueBallPointForCheck.c += direction.c;

		if (maze[blueBallPointForCheck.r][blueBallPointForCheck.c] == 'O') {
			blueBallInHole = true;
			break;
		}
	}

}

void moveBlueBallFirst(Point direction, int idx) {

	while (maze[blueBallPointForCheck.r + direction.r][blueBallPointForCheck.c + direction.c] != '#' &&
		!(redBallPointForCheck.r == blueBallPointForCheck.r + direction.r && redBallPointForCheck.c == blueBallPointForCheck.c + direction.c)
		) {
		blueBallPointForCheck.r += direction.r;
		blueBallPointForCheck.c += direction.c;

		if (maze[blueBallPointForCheck.r][blueBallPointForCheck.c] == 'O') {
			blueBallPointForCheck.r = -1;
			blueBallPointForCheck.c = -1;
			blueBallInHole = true;
			break;
		}
	}

	while (maze[redBallPointForCheck.r + direction.r][redBallPointForCheck.c + direction.c] != '#' &&
		!(redBallPointForCheck.r + direction.r == blueBallPointForCheck.r && redBallPointForCheck.c + direction.c == blueBallPointForCheck.c)
		) {
		redBallPointForCheck.r += direction.r;
		redBallPointForCheck.c += direction.c;

		if (maze[redBallPointForCheck.r][redBallPointForCheck.c] == 'O') {
			redBallInHole = true;
			break;
		}
	}
}

매개변수로 현재 고려되는 방향을 입력받는다. (원래는 idx는 입력받을 필요없다.)

후에, 구슬의 다음으로 이동하는 좌표가

  1. 벽이 아니고
  2. 각 구슬의 현재 좌표가 반대 구슬의 좌표가 아니라면

계속 이동시켜주며, 먼저 이동한 구슬이 구멍에 들어갔을 경우, r과 c를 {-1, -1}로 초기화한다.

초기화 하지 않으면, 예를 들어 빨간 구슬이 먼저 구멍에 들어갔고 파란 구슬이 구멍에 들어갈 수 있는데,

빨간 구슬이 이미 해당 좌표에 있으므로 파란 구슬이 들어가지 않게 된다. 따라서 오답을 내게 된다.