[백준] 13460: 구슬 탐험 (with C++)
안녕하세요?
보실실입니다.
아무도 대답해주지 않지만 어차피 제 기록용이라 상관 없습니다. 저는 지금 아주 행복합니다. 왜냐하면 그저께까지 난 왜이렇게 바보일까, BFS 변형해서 푸는 그 문제 못풀었다고 슬퍼하고 있었던 것과는 반대로, 오늘은 BFS를 활용하는 문제를 순식간에 풀었기 때문입니다. 아 정말 행복하다. 나 조금은 성장하고 있을지도...데헷? 정신차려라 이 문제가 더 쉬운 거였다.
문제
https://www.acmicpc.net/problem/13460
스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.
보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.
이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.
각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.
보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.
보자마자 진짜 자신 있었지만 내가 짠 코드는 꽤 길어서 시간이 좀 걸렸던 문제이다. 본인이 골딱이인 관계로 골드1 문제는 일명 <맞왜틀!!!(맞았는데 왜 틀렸습니다가 나와!!!)> 과정을 거치는 경우가 왕왕 있는데,, 의외로 바로 통과. 제발 시험장에서도 이럴 수 있었으면 좋겠다.
[구상]
1. BFS로 모든 이동방향을 탐색하면서 최소 이동값을 찾아야 한다.
2. 10 이하의 이동만 허용하므로 깊이 10으로 제한한다.
3. 큐에 현재 R, B의 위치와 움직인 횟수를 하나의 세트로 push 및 pop한다.
4. 큐의 front 원소에 대해, 4방향으로 기울이면서 변화한 R과 B의 위치를 확인한다.
5. 만약 R과 B의 위치가 변했으며, B가 구멍으로 떨어지지 않았으며, R이 구멍으로 떨어지지 않으면 현재 위치와 이동 횟수를 큐에 넣는다.
(구슬들의 위치가 변하지 않았거나 B가 구멍으로 떨어졌으면 이 가지에 대한 탐색 중지, R이 구멍으로 떨어졌으면 이동값을 현재까지 탐색에서의 최솟값과 비교해서 최솟 이동값을 저장.)
6. 위 과정을 움직인 횟수 10 이하인 노드들에 대해서만 반복한다.
[주의사항]
나는 코드가 복잡해지는 것이 싫어서 구슬을 이동시키는 함수는 따로 짰다. 벽 만나면 정지시키고, 두 구슬이 겹치면 원래위치 기반으로 안겹치게 재조정하고, 구멍에 겹치는 경우에는 그대로 뒀다. 그리고 맵 정보는 R이나 B의 초기 위치에 빈 공간을 대입하는 식으로 저장했다. 굳이 맵을 바꿀 필요는 없고, 경우도 많은데 복잡하게 하고 싶지 않았다. 그리고 또 좌표로 치면 왼쪽 상단이 원점, 세로가 x축 가로가 y축인 형태로 풀었다. 이게 입력을 받기 더 편해서 거의 모든 문제를 이렇게 풀고 있는데, 언젠간 헷갈릴 날이 올 것도 같아서 걱정되긴 한다. 더 익숙해지지 뭐...
[코드]
전혀 깔끔하지 않다. 특히 move 함수가 여러 경우를 처리하려다 보니 많이 복잡해졌다. node도 저 구조가 최선은 아닐텐데...
#include<iostream>
#include<queue>
#include<climits>
using namespace std;
char** board;
int n;
int m;
struct node {
int R[2];
int B[2];
int move;
void init(int* _R, int* _B, int _move) {
R[0] = *_R;
R[1] = *(_R + 1);
B[0] = *_B;
B[1] = *(_B + 1);
move = _move;
}
};
node move(int* R, int* B, int direction, int move) {
node result;
result.init(R, B, move);
int r_x = result.R[0];
int r_y = result.R[1];
int b_x = result.B[0];
int b_y = result.B[1];
if(direction == 0) {
//up
while (board[r_x-1][r_y] == '.') {
r_x -= 1;
}
if(board[r_x-1][r_y] == 'O'){
r_x -= 1;
}
result.R[0] = r_x;
while (board[b_x-1][b_y] == '.') {
b_x -= 1;
}
if(board[b_x-1][b_y] == 'O'){
b_x -= 1;
}
result.B[0] = b_x;
if(!(board[r_x][r_y] == 'O') && result.R[0] == result.B[0] && result.R[1] == result.B[1]) {
if(*R > *B) {
result.R[0] = r_x + 1;
}
else {
result.B[0] = b_x + 1;
}
}
}
else if (direction == 1) {
//down
while (board[r_x+1][r_y] == '.') {
r_x += 1;
}
if(board[r_x+1][r_y] == 'O'){
r_x += 1;
}
result.R[0] = r_x;
while (board[b_x+1][b_y] == '.') {
b_x += 1;
}
if(board[b_x+1][b_y] == 'O'){
b_x += 1;
}
result.B[0] = b_x;
if(!(board[r_x][r_y] == 'O') && result.R[0] == result.B[0] && result.R[1] == result.B[1]) {
if(*R < *B) {
result.R[0] = r_x - 1;
}
else {
result.B[0] = b_x - 1;
}
}
}
else if (direction == 2) {
//right
while (board[r_x][r_y+1] == '.') {
r_y += 1;
}
if(board[r_x][r_y+1] == 'O'){
r_y += 1;
}
result.R[1] = r_y;
while (board[b_x][b_y+1] == '.') {
b_y += 1;
}
if(board[b_x][b_y+1] == 'O'){
b_y += 1;
}
result.B[1] = b_y;
if(!(board[r_x][r_y] == 'O') && result.R[0] == result.B[0] && result.R[1] == result.B[1]) {
if(*(R+1) < *(B+1)) {
result.R[1] = r_y - 1;
}
else {
result.B[1] = b_y - 1;
}
}
}
else {
//left
while (board[r_x][r_y-1] == '.') {
r_y -= 1;
}
if(board[r_x][r_y-1] == 'O'){
r_y -= 1;
}
result.R[1] = r_y;
while (board[b_x][b_y-1] == '.') {
b_y -= 1;
}
if(board[b_x][b_y-1] == 'O'){
b_y -= 1;
}
result.B[1] = b_y;
if( !(board[r_x][r_y] == 'O') && result.R[0] == result.B[0] && result.R[1] == result.B[1]) {
if(*(R+1) > *(B+1)) {
result.R[1] = r_y + 1;
}
else {
result.B[1] = b_y + 1;
}
}
}
result.move += 1;
return result;
}
int main(int argc, char** argv)
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
board = new char*[n];
int R[2];
int B[2];
int min = INT_MAX;
for (int i=0; i<n; i++) {
board[i] = new char[m];
for (int j=0; j<m; j++) {
cin >> board[i][j];
if (board[i][j] == 'R') {
R[0] = i;
R[1] = j;
board[i][j] = '.';
}
else if (board[i][j] == 'B') {
B[0] = i;
B[1] = j;
board[i][j] = '.';
}
}
}
queue<node> q;
node first;
first.init(R, B, 0);
q.push(first);
while(!q.empty()) {
node now = q.front();
q.pop();
if(now.move == 10) {
continue;
}
for(int i=0; i<4; i++) {
node moved = move(now.R, now.B, i, now.move);
if(moved.R[0] == now.R[0] && moved.R[1] == now.R[1] && moved.B[0] == now.B[0] && moved.B[1] == now.B[1] ) {
continue;
}
if(board[moved.B[0]][moved.B[1]] == 'O') {
continue;
}
if(board[moved.R[0]][moved.R[1]] == 'O') {
if(min > moved.move){
min = moved.move;
}
continue;
}
q.push(moved);
}
}
if(min > 10) {
cout << "-1\n";
}
else {
cout << min << "\n";
}
return 0;
}