슈뢰딩거의 고등어
13460 구슬탈출2 본문
https://www.acmicpc.net/problem/13460
13460번: 구슬 탈출 2
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'
www.acmicpc.net
위, 아래, 오른쪽, 왼쪽으로 기울일 경우 구할수 있는 새로운 위치를 각 구슬별로 while 문으로 구한후
만약 구슬의 위치가 겹칠 경우, 현재 위치~새로운 위치 거리로 선수위, 후순위를 구한다.
또한 구슬의 위치(방문)을 저장하기 위해 visit[rx][ry][bx][by]를 구한다.
이 문제에서는 x, y 의 위치가 일반적으로 사용하는 y, x 가 아닌 x, y 임을 유의한다.
또한, 최대 탐색 횟수 조건이 있을 경우, 그 조건을 가장 상단에 위치하여 먼저 횟수를 확인하도록 한다.
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
/*
빨간 구슬과 파란 구슬을 하나씩 넣은 다음,
빨간 구슬을 구멍을 통해 빼내는 게임이다
파란 구슬이 구멍에 들어가면 안 된다.
중력을 이용해서 이리 저리 굴려야 한다.
왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기
공은 동시에 움직인다.
빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다.
빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다.
기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.
최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오. (BFS)
*/
struct INFO {
int by, bx, ry, rx; // 위치
int cnt;
};
int n,m;
INFO start;
int answer = -1;
string map[11];
int dx[] = {1, 0, 0, -1};
int dy[] = {0, 1, -1, 0};
void BFS() {
bool visit[10][10][10][10] = { false };
queue <INFO> q;
q.push(start);
visit[start.rx][start.ry][start.bx][start.by] = true;
while(!q.empty()) {
INFO cur = q.front(); q.pop();
if(cur.cnt > 10)
return;
if(map[cur.rx][cur.ry] == 'O' && map[cur.bx][cur.by] != 'O') {
answer = cur.cnt;
return;
}
//왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기
for(int i=0; i<4; i++) {
int next_rx = cur.rx;
int next_ry = cur.ry;
int next_bx = cur.bx;
int next_by = cur.by;
// 빨간공이 벽에 닿을때까지 간다.
while(1) {
// .
if (map[next_rx][next_ry] != '#' && map[next_rx][next_ry] != 'O') {
next_rx += dx[i];
next_ry += dy[i];
}
// # or O
else {
// #
if(map[next_rx][next_ry] == '#') {
next_rx -= dx[i];
next_ry -= dy[i];
}
break;
}
}
// 파란공이 벽에 닿을때까지 간다.
while(1) {
// .
if (map[next_bx][next_by] != '#' && map[next_bx][next_by] != 'O') {
next_bx += dx[i];
next_by += dy[i];
}
// # or O
else {
// #
if(map[next_bx][next_by] == '#') {
next_bx -= dx[i];
next_by -= dy[i];
}
break;
}
}
// 둘이 겹쳤을 경우 더 많이 움직인쪽을 하나 백한다.
if(next_rx == next_bx && next_ry == next_by) {
if(map[next_rx][next_ry] != 'O') {
int red_dist = abs(next_ry - cur.ry) + abs(next_rx - cur.rx);
int blue_dist = abs(next_by - cur.by) + abs(next_bx - cur.bx);
if (red_dist >= blue_dist) {
next_rx -= dx[i];
next_ry -= dy[i];
}
else {
next_bx -= dx[i];
next_by -= dy[i];
}
}
}
// 방문확인
if(visit[next_rx][next_ry][next_bx][next_by] == false) {
visit[next_rx][next_ry][next_bx][next_by] = true;
INFO next;
next.rx = next_rx;
next.ry = next_ry;
next.bx = next_bx;
next.by = next_by;
next.cnt = cur.cnt + 1;
q.push(next);
}
}
}
}
int main() {
scanf("%d %d", &n, &m);
for(int i=0; i<n; i++) {
cin >> map[i];
for (int j=0; j<m; j++) {
if(map[i][j] == 'R') {
start.rx = i;
start.ry = j;
}
if(map[i][j] == 'B') {
start.bx = i;
start.by = j;
}
}
}
start.cnt = 0;
BFS();
printf("%d\n", answer);
return 0;
}
이전에 작성했던 코드
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
struct TURN {
int by, bx, ry, rx; // 위치
int sec;
int game_end = 0; // 0 continue 1 win 2 lose
};
// y, x
int n, m, answer;
int blank_y, blank_x;
vector <string> arr;
// 왼쪽으로 기울이기
TURN up(TURN turn) {
int cur_by = turn.by;
int cur_bx = turn.bx;
int cur_ry = turn.ry;
int cur_rx = turn.rx;
bool b_success = false;
bool r_success = false;
int move = 0;
// do blue first
if(cur_by < cur_ry) {
// move blue
while(true) {
move++;
if(cur_by - move == blank_y && cur_bx == blank_x) {
b_success = true; // lose
break;
}
if(arr[cur_by-move][cur_bx] != '.') {
move--;
break;
}
}
if(move > 0) {
turn.by = cur_by - move;
}
move = 0;
// move red
while(true) {
move++;
if(cur_ry - move == blank_y && cur_rx == blank_x) {
r_success = 1; // win
break;
}
if(arr[cur_ry - move][cur_rx] != '.') {
move--;
break;
}
}
if(move > 0) {
turn.ry = cur_ry - move;
}
}
else {
// move red
while(true) {
move++;
if(cur_ry - move == blank_y && cur_rx == blank_x) {
r_success = 1; // win
break;
}
if(arr[cur_ry - move][cur_rx] != '.') {
move--;
break;
}
}
if(move > 0) {
turn.ry = cur_ry - move;
}
// move blue
move = 0;
while(true) {
move++;
if(cur_by - move == blank_y && cur_bx == blank_x) {
b_success = true; // lose
break;
}
if(arr[cur_by-move][cur_bx] != '.') {
move--;
break;
}
}
if(move > 0) {
turn.by = cur_by - move;
}
}
if(b_success)
turn.game_end = 2;
else if(r_success)
turn.game_end = 1;
else
turn.game_end = 0;
turn.sec++;
return turn;
}
TURN down(TURN turn) {
int cur_by = turn.by;
int cur_bx = turn.bx;
int cur_ry = turn.ry;
int cur_rx = turn.rx;
turn.sec++;
bool b_success = false;
bool r_success = false;
int move = 0;
// do blue first
if(cur_by > cur_ry) {
// move blue
while(true) {
move++;
if(cur_by + move == blank_y && cur_bx == blank_x) {
b_success = true; // lose
break;
}
if(arr[cur_by+move][cur_bx] != '.' ) {
move--;
break;
}
}
if(move > 0) {
turn.by = cur_by + move;
if(b_success) {
turn.game_end = 2;
return turn;
}
}
move = 0;
// move red
while(true) {
move++;
if(cur_ry + move == blank_y && cur_rx == blank_x) {
r_success = true; // win
break;
}
if(arr[cur_ry +move][cur_rx] != '.') {
move--;
break;
}
}
if(move > 0) {
turn.ry = cur_ry + move;
if(r_success) {
turn.game_end = 1;
return turn;
}
}
}
else {
// move red
while(true) {
move++;
if(cur_ry + move == blank_y && cur_rx == blank_x) {
r_success = true; // win
break;
}
if(arr[cur_ry +move][cur_rx] != '.') {
move--;
break;
}
}
if(move > 0) {
turn.ry = cur_ry + move;
}
move = 0;
// move blue
while(true) {
move++;
if(cur_by + move == blank_y && cur_bx == blank_x) {
b_success = true; // lose
break;
}
if(arr[cur_by+move][cur_bx] != '.' ) {
move--;
break;
}
}
if(move > 0) {
turn.by = cur_by + move;
if(b_success) {
turn.game_end = 2;
return turn;
}
}
}
if(b_success)
turn.game_end = 2;
else if(r_success)
turn.game_end = 1;
else
turn.game_end = 0;
return turn;
}
// 왼쪽으로 기울이기
TURN left(TURN turn) {
int cur_by = turn.by;
int cur_bx = turn.bx;
int cur_ry = turn.ry;
int cur_rx = turn.rx;
turn.sec++;
bool b_success = false;
bool r_success = false;
int r_move = 0;
int b_move = 0;
// do blue first
if(cur_bx < cur_rx) {
// move blue
while(true) {
b_move++;
if(cur_by==blank_y && cur_bx - b_move == blank_x) {
b_success = true; // lose
break;
}
if(arr[cur_by][cur_bx-b_move] != '.') {
b_move--;
break;
}
}
if(b_move > 0) {
turn.bx = cur_bx - b_move;
if(b_success) {
turn.game_end = 2;
return turn;
}
}
r_move = 0;
while(true) {
r_move++;
if(cur_ry == blank_y && cur_rx - r_move == blank_x) {
r_success= true; // win
break;
}
if(arr[cur_ry][cur_rx-r_move] != '.') {
r_move--;
break;
}
}
if(r_move > 0) {
turn.rx = cur_rx - r_move;
}
}
else {
while(true) {
r_move++;
if(cur_ry == blank_y && cur_rx - r_move == blank_x) {
r_success= true; // win
break;
}
if(arr[cur_ry][cur_rx-r_move] != '.') {
r_move--;
break;
}
}
if(r_move > 0) {
turn.rx = cur_rx - r_move;
if(r_success) {
turn.game_end = 1;
return turn;
}
}
int b_move = 0;
while(true) {
b_move++;
if(cur_by==blank_y && cur_bx - b_move == blank_x) {
b_success = true; // lose
break;
}
if(arr[cur_by][cur_bx-b_move] != '.') {
b_move--;
break;
}
}
if(b_move > 0) {
turn.bx = cur_bx - b_move;
}
}
//printf("%d %d %d %d\n", b_success, b_move, r_success, r_move);
if (b_success && r_success) {
if(r_move < b_move){
turn.game_end = 1;
}
else
turn.game_end = 2;
}
else if(b_success)
turn.game_end = 2;
else if(r_success)
turn.game_end = 1;
else
turn.game_end = 0;
return turn;
}
// 오른쪽으로 기울이기
TURN right(TURN turn) {
int cur_by = turn.by;
int cur_bx = turn.bx;
int cur_ry = turn.ry;
int cur_rx = turn.rx;
bool b_success = false;
bool r_success = false;
int b_move = 0;
//printf("Blank %d %d\n", blank_x, blank_y);
if(cur_bx > cur_ry) {
// move blue
while(true) {
b_move++;
if(cur_by==blank_y && cur_bx + b_move == blank_x) {
b_success = true; // lose
break;
}
if(arr[cur_by][cur_bx+b_move] != '.') {
b_move--;
break;
}
}
if(b_move > 0) {
turn.bx = cur_bx + b_move;
}
// red
int r_move = 0;
while(true) {
r_move++;
if(cur_ry == blank_y && cur_rx + r_move == blank_x) {
r_success = true; // win
break;
}
if(arr[cur_ry][cur_rx+r_move] != '.') {
r_move--;
break;
}
}
if(r_move > 0) {
turn.rx = cur_rx + r_move;
}
}
else {
// red
int r_move = 0;
while(true) {
r_move++;
if(cur_ry == blank_y && cur_rx + r_move == blank_x) {
r_success = true; // win
break;
}
if(arr[cur_ry][cur_rx+r_move] != '.') {
r_move--;
break;
}
}
if(r_move > 0) {
turn.rx = cur_rx + r_move;
}
int b_move = 0;
// move blue
while(true) {
b_move++;
if(cur_by==blank_y && cur_bx + b_move == blank_x) {
b_success = true; // lose
break;
}
if(arr[cur_by][cur_bx+b_move] != '.') {
b_move--;
break;
}
}
if(b_move > 0) {
turn.bx = cur_bx + b_move;
}
}
//printf("R: %d %d\n", turn.rx, turn.ry);
//printf("r: %d b: %d\n", r_move, b_move);
if(b_success)
turn.game_end = 2;
else if(r_success)
turn.game_end = 1;
else
turn.game_end = 0;
turn.sec++;
return turn;
}
void BFS() {
queue <TURN> q;
TURN game;
game.sec = 0;
for(int i=0; i<arr.size(); i++)
for(int j=0; j<arr[0].size(); j++) {
if(arr[i][j] == 'B') {
arr[i][j] ='.';
game.by = i;
game.bx = j;
}
else if(arr[i][j] == 'R') {
arr[i][j] = '.';
game.ry = i;
game.rx = j;
}
else if(arr[i][j] != '#' && arr[i][j] != '.') {
blank_y = i;
blank_x = j;
}
}
q.push(game);
while(!q.empty()) {
//printf("while");
TURN cur = q.front();
q.pop();
if(cur.game_end == 1) {
answer = cur.sec;
return;
}
if(cur.sec >= 10) {
answer = -1;
return;
}
TURN next_turn;
//왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기
next_turn = left(cur);
if (next_turn.game_end != 2)
q.push(next_turn);
next_turn = right(cur);
if (next_turn.game_end != 2)
q.push(next_turn);
next_turn = up(cur);
if (next_turn.game_end != 2)
q.push(next_turn);
next_turn = down(cur);
if (next_turn.game_end != 2)
q.push(next_turn);
}
}
int main() {
scanf("%d %d", &n, &m);
for(int i=0; i<n; i++) {
string tmp = "";
cin >> tmp;
arr.push_back(tmp);
}
BFS();
printf("%d\n",answer);
return 0;
}
'알고리즘' 카테고리의 다른 글
| 오픈채팅방 (0) | 2021.12.21 |
|---|---|
| 14499 주사위굴리기 (0) | 2021.12.19 |
| 21609 상어중학교 (0) | 2021.12.13 |
| 21608 상어초등학교 (0) | 2021.12.11 |
| 14888 연산자 끼워넣기 ( DFS : 중복순열 || next_permutation) (0) | 2021.12.10 |
'알고리즘' Related Articles
more
Comments