[백준 13460번] 구슬 탈출 2

난이도: 골드 2

문제 링크: www.acmicpc.net/problem/13460

출처: 삼성 SW역량 테스트

13460번: 구슬 탈출 2

백준 13460번 문제 구슬 탈출 2

앞서 다룬 2048 (easy) 와 유사한 성격의 문제입니다.

구슬 탈출 미로 장난감

대략 위처럼 생긴 장난감이 있는 상황입니다. 단, 테두리는 전부 벽으로 막혀 있고, 위 사진과는 다르게 탈출구는 특정 위치의 바닥에 뚫려 있습니다. 또, 구슬이 파란색과 빨간색 두 개가 있는데, 파란색을 빼지 않고 빨간색을 빼야 성공입니다.

 

시뮬레이션 성격을 겸하는 완전탐색 문제로, DFS와 BFS 양 방법으로 문제를 풀 수 있습니다.

저는 코드를 간단하게 적는 것을 좋아해서 DFS를 이용한 재귀 형식으로 접근했습니다.

 

입력은 다음과 같이 들어옵니다:

 

#	#	#	#	#	#	#
#	.	.	.	R	B	#
#	.	#	#	#	#	#
#	.	.	.	.	.	#
#	#	#	#	#	.	#
#	O	.	.	.	.	#
#	#	#	#	#	#	#

#은 벽, .은 빈 공간을 의미하며, R은 빨간 구슬, B는 파란 구슬, O는 탈출구입니다.

각 구슬은 같은 공간에 존재할 수 없습니다. 예를 들어 위 상황에서 장난감을 왼쪽으로 기울이면, board[1][1]에 R, board[1][2]에 B가 위치합니다.

장난감은 상하좌우로 기울일 수 있으며, 최대 10회 이내에 빨간 구슬이 탈출하는 동시에 파란 구슬은 탈출하지 못한다면, 그 횟수를 출력합니다. 만약 위 조건을 10회 이내에 만족할 수 없다면 -1을 출력합니다.

 

DFS를 이용한 접근 방식은 2048(easy) 문제와 완전히 동일합니다. C++로 코드를 작성할 때 배열을 복사하여 사용하고 인자로 넘기는 부분 역시 동일합니다.

따라서 가장 문제가 되는 점은 역시 시뮬레이션 부분입니다. 구슬이 겹칠 수 없으며, 장난감을 기울일 때 구슬이 움직여야 하고, 탈출구에 도달하면 구슬이 소멸할 때, 빨간 구슬만 탈출하고 파란 구슬은 탈출하지 않은 경우만을 성공으로 인정합니다.

 

제가 접근한 방법은 다음과 같습니다.

1. board[1]의 맨 처음과 맨 마지막은 #이므로, board[1][1]부터 검사를 시작합니다.
2. board[1][j]가 구슬이 아닐 경우 (O, ., #), 아무것도 하지 않고 넘어갑니다. 구슬인 경우, 파란 구슬인지 빨간 구슬인지 여부를 now에 저장합니다.
3. 현재 구슬의 위치부터 시작해서, board[1][1]이 될 때까지 거슬러 올라갑니다. .일 경우, 두 배열의 값을 바꾸어, 구슬의 위치를 빈 칸으로 1칸 이동시킵니다. O일 경우, 구슬을 없애고, 해당 색깔의 구슬이 들어갔음을 확인하는 bool 변수 blueEnter 혹은 redEnter를 활성화 시키고, 거슬러 올라가는 것을 종료합니다. 이외의 경우 (#), 거슬러 올라가는 것을 종료합니다.
4. 모든 행을 기준으로 한 구슬들의 이동이 끝났으면, blueEnter와 redEnter를 확인합니다. blueEnter가 활성화 되었을 경우, 조건에 부합하지 않으므로 탐색 실패로 간주하고 더 이상 탐색하지 않습니다. blueEnter가 비활성화이며 redEnter가 활성화인 경우, 탐색이 성공적으로 완료되었다고 가정하고, 현재의 탐색 깊이를 글로별 변수 turn과 비교하여, 더 작은 값을 turn에 저장합니다. 둘 다 아닌 경우, 즉 redEnter와 blueEnter 모두 비활성화인 경우, 탐색 depth를 하나 늘리고, 함수를 재귀 호출하여 탐색을 진행합니다. 단, 현재 방향과 다음 방향이 같은 경우에는 함수를 재귀 호출하지 않습니다.

위 테스트 케이스의 board[1] 행을 기준으로 생각해 보겠습니다. 즉, board[1] = {#, ., ., ., R, B, #} 입니다. 이를 왼쪽으로 기울였을 때를 생각해 봅시다.

먼저, board[1][1]을 검사합니다. 값이 ., 즉 빈칸이므로, 아무것도 하지 않고 넘어갑니다.

1. 마찬가지로, board[1][2], board[1][3] 역시 빈칸이므로 아무것도 하지 않고 넘어갑니다.
2. board[1][4]를 검사합니다. R이므로 구슬이며, 정확히는 빨간 구슬입니다. 따라서 R을 이전의 값들과 거슬러 올라가며 차례로 비교합니다. board[1][3]의 값은 .이므로, 두 값을 서로 교환합니다. board[1][3] = R, board[1][4] = . 이 됩니다. 이를 반복하면 board[1][1] = R, board[1][2] = ., board[1][3] = ., board[1][4] = . 이 됩니다. 마지막으로 board[1][0] 의 값은 #이므로, 교환하지 않고 종료합니다.
3. board[1][5]를 검사합니다. B이므로 구슬이며, 정확히는 파란 구슬입니다. 앞의 과정과 비슷하게, 구슬과 빈칸의 값을 거슬러 올라가며 교환합니다. board[1][2]의 값이 B가 되었을 때, board[1][1]의 값은 R이므로, 교환하지 않고 종료합니다.
4. board[1][6]은 맨 끝자리의 가장자리 벽이므로 검사하지 않고 종료합니다.

위 과정이 완료된 후 board[1] = {#, R, B, ., ., ., #} 가 됩니다. 문제에서 요구한 조건대로 공이 움직였음을 확인할 수 있습니다.

 

위 로직을 이용하여 상하좌우 각각에 대해 구현해 주면 됩니다. 역시 배열의 인자를 적을 때 매우 주의하여야 하며, 코드가 길기 때문에 한번 틀리게 되면 틀린 점을 찾기 쉽지 않습니다. 

 

또 자주 틀리는 경우 중 입력이 다음과 같이 들어올 때가 있습니다.

#####

#BRO#

#####

위의 경우, 문제의 요구 조건에 따르면 오답입니다. 오른쪽으로 기울이면 R이 탈출하지만, 동시에 B도 탈출하기 때문입니다.

마지막으로, 움직임 10회 이내에 답을 얻을 수 없을 경우 -1을 출력해야 합니다. 이 조건 역시 자주 간과하는 부분이므로 신경 쓰시기 바랍니다.

 

	#include <iostream>
	using namespace std;
	#define MAX_N 10
	int n, m, turn = 1e9;
	void array_copy (char from[][MAX_N], char to[][MAX_N]) {
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	to[i][j] = from[i][j];
	}
	}
	}
	void simulate(int index, char arr[][MAX_N], int dir) {
	char copy[MAX_N][MAX_N];
	array_copy(arr, copy);
	if (index == 10) return;
	bool blueEnter = false, redEnter = false;
	if (dir == 0) { //왼쪽으로 기울일 때
	for (int i = 0; i < n; i++) {
	for (int j = 1; j < m; j++) {
	if (copy[i][j] == 'B' || copy[i][j] == 'R') {
	char now = copy[i][j];
	for (int k = j; k > 0; k--) {
	if (copy[i][k-1] == '.') {
	swap(copy[i][k], copy[i][k-1]);
	continue;
	}
	else if (copy[i][k-1] == 'O') {
	if (now == 'B') blueEnter = true;
	else if (now == 'R') redEnter = true;
	copy[i][k] = '.';
	break;
	}
	else break;
	}
	}
	}
	}
	}
	else if (dir == 1) { //오른쪽으로 기울일 때
	for (int i = 0; i < n; i++) {
	for (int j = m-2; j >= 0; j--) {
	if (copy[i][j] == 'B' || copy[i][j] == 'R') {
	char now = copy[i][j];
	for (int k = j; k < m; k++) {
	if (copy[i][k+1] == 'O') {
	if (now == 'B') blueEnter = true;
	else if (now == 'R') redEnter = true;
	copy[i][k] = '.';
	break;
	}
	else if (copy[i][k+1] == '.') {
	swap(copy[i][k], copy[i][k+1]);
	continue;
	}
	else break;
	}
	}
	}
	}
	}
	else if (dir == 2) { //위쪽으로 기울일 때
	for (int j = 0; j < m; j++) {
	for (int i = 1; i < n; i++) {
	if (copy[i][j] == 'B' || copy[i][j] == 'R') {
	char now = copy[i][j];
	for (int k = i; k > 0; k--) {
	if (copy[k-1][j] == '.') {
	swap(copy[k][j], copy[k-1][j]);
	continue;
	}
	else if (copy[k-1][j] == 'O') {
	if (now == 'B') blueEnter = true;
	else if (now == 'R') redEnter = true;
	copy[k][j] = '.';
	break;
	}
	else break;
	}
	}
	}
	}
	}
	else if (dir == 3) { //아래쪽으로 기울일 때
	for (int j = 0; j < m; j++) {
	for (int i = n-2; i >= 0; i--) {
	if (copy[i][j] == 'B' || copy[i][j] == 'R') {
	char now = copy[i][j];
	for (int k = i; k < n; k++) {
	if (copy[k+1][j] == 'O') {
	if (now == 'B') blueEnter = true;
	else if (now == 'R') redEnter = true;
	copy[k][j] = '.';
	break;
	}
	else if (copy[k+1][j] == '.') {
	swap(copy[k][j], copy[k+1][j]);
	continue;
	}
	else break;
	}
	}
	}
	}
	}
	if (redEnter && !blueEnter) {
	turn = min(turn, index + 1);
	return;
	}
	else if (blueEnter) return;
	for (int nextDir = 0; nextDir < 4; nextDir++) {
	if (dir == nextDir) continue;
	simulate(index+1, copy, nextDir);
	}
	}
	int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	char board[MAX_N][MAX_N];
	cin >> n >> m;
	for (int i = 0; i < n; i++) { //세로
	for (int j = 0; j < m; j++) { //가로
	cin >> board[i][j];
	}
	}
	for (int dir = 0; dir < 4; dir++) {
	simulate(0, board, dir);
	}
	if (turn == 1e9) cout << -1;
	else cout << turn;
	return 0;
	}

view raw 13460_구슬탈출2.cpp hosted with ❤ by GitHub

채점 결과

저도 사소한 오타 두 개를 찾지 못해 문제를 푸는데 많은 고생을 했습니다... ㅠㅠ

정확히 틀리는 지점이 어디인지 확인하려고 제출을 여러 번 하기도 했지만, 이런 문제는 각 방향별로 코드를 따로 작성하므로 잘못된 점을 찾기가 정말 쉽지 않습니다. 오타에 특히 주의하시길 다시 한 번 당부드립니다.

 

해당 문제와 같은 시리즈의 다른 문제들을 소개합니다:

• 구슬 탈출: 난이도 골드 3, 링크 www.acmicpc.net/problem/13459
• 구슬 탈출 3: 난이도 골드 2, 링크 www.acmicpc.net/problem/15644
• 구슬 탈출 4: 난이도 골드 2, 링크 www.acmicpc.net/problem/15653
• Maze: 난이도 플래티넘 5, 링크 www.acmicpc.net/problem/10218