[BFS][삼성기출]백준13460번 구슬탈출2
업데이트:
백준13460 구슬탈출2
머리 속으로는 어떻게 풀어야할지 느낌이 오는데 구현으로 풀어내려니 갑갑했던 문제였다.
게다가 학기가 시작하고 프로젝트부터 인턴 자소서까지 바쁜 일들을 핑계삼다보니 문제를 너무 오랜만에 풀어 구현을 할래야 손이 움직이지 않아 할 수가 없었다.
결국 한참을 붙잡고나서야 풀 수 있었는데, 정말 알고리즘 문제는 꾸준히 풀어야 한다는 걸 느끼게 됐다.
빨간 구슬을 구멍에 넣을 수 있는 최소 횟수를 구해야 한다.
최소 횟수를 구하는 문제이기 때문에 BFS를 사용해야겠다고 생각했다.
그런데 잘못 생각했던 점은 빨간 구슬과 파란 구슬을 각자 큐에 넣고 돌리려고 했다는 것이다.
두 개의 구슬을 함께 움직여야 하고, 하나의 포지션에서 움직일 수 있는 경우의 수는 4개이기 때문에 Queue에 무엇을 넣을지 고민해야 했다.
구현이 복잡해 질 것 같아 다음과 같이 구슬 구조체를 만들었다.
struct ball{
int y, x, time;
char type;
pair<int,int> pre_dir;
};
구슬 구조체는 좌표를 나타내는 y,x와 구슬이 몇 번 움직인 상태인지 나타내는 time 변수, 구슬의 색을 나타낼 type 변수, 마지막에 어떤 방향으로 기울여져서 현재 위치에 있게 되었는지를 나타내는 pre_dir 변수가 있다.
pre_dir 변수가 필요한 이유는 방금전에 왔던 방향으로는 다시 가지 않아야 하기 때문이다. 예를 들어, 구슬을 오른쪽으로 기울인 다음에는 다시 왼쪽으로 기울이지 않아야 한다.
구슬을 기울이는 경우에 각 구슬은 자신이 더 이상 움직이지 못할 때까지 움직여야 한다.
움직이지 못하는 경우는 벽을 만났을 때나, 구멍에 빠졌을 때이다.
구슬이 움직이는 경우는 따로 함수로 구현하였다.
pair<struct ball, struct ball> tilt(int y_dir,int x_dir,struct ball red, struct ball blue){
struct ball rB;
struct ball bB;
rB.y = red.y;
rB.x = red.x;
bB.y = blue.y;
bB.x = blue.x;
rB.time = red.time+1;
bB.time = blue.time+1;
rB.pre_dir.first = y_dir;
rB.pre_dir.second = x_dir;
bB.pre_dir.first = y_dir;
bB.pre_dir.second = x_dir;
//move red ball
while(1){
if(rB.y + y_dir >= 0 && rB.x + x_dir >=0 && rB.y + y_dir < N && rB.x + x_dir < M){
rB.y += y_dir;
rB.x += x_dir;
}
if(board[rB.y][rB.x] == '#'){
rB.y -= y_dir;
rB.x -= x_dir;
break;
}
if(board[rB.y][rB.x] == 'O'){
break;
}
}
// move blue ball
while(1){
if(bB.y + y_dir >= 0 && bB.x + x_dir >=0 && bB.y + y_dir < N && bB.x + x_dir < M){
bB.y += y_dir;
bB.x += x_dir;
}
if(board[bB.y][bB.x] == '#'){
bB.y -= y_dir;
bB.x -= x_dir;
break;
}
if(board[bB.y][bB.x] == 'O'){
break;
}
}
// when both balls are in same position
if(rB.y == bB.y && rB.x == bB.x && !(board[rB.y][rB.x] == 'O' && board[bB.y][bB.x]=='O')){
if(red.x == blue.x){
//down
if(y_dir == 1){
if(red.y < blue.y){
rB.y -= 1;
}
else {
bB.y -= 1;
}
}
else if(y_dir==-1){
if(red.y < blue.y){
bB.y++;
}
else {
rB.y++;
}
}
}
else if(red.y == blue.y){
if(x_dir==1){
if(red.x < blue.x){
rB.x--;
}
else{
bB.x--;
}
}
else if(x_dir==-1){
if(red.x < blue.x){
bB.x++;
}
else {
rB.x++;
}
}
}
}
return make_pair(rB,bB);
}
구슬을 움직이는 tilt 함수는 매개변수로 자신이 움직일 방향과 구슬 두 개를 받는다.
함수는
- 빨간 구슬 굴리기
- 파란 구슬 굴리기
- 둘이 겹치는 경우 처리하기
를 수행한다.
1번이나 2번은 쉽게 생각할 수 있는데, 3번 둘이 겹치는 경우를 잘 처리해줘야 한다.
만약 두 구슬이 같은 위치에 있는 경우, 굴리기 전의 위치를 참고하여 조정을 해줘야 한다.
다음과 같은 경우들이 나온다.
- 아래로 기울인 경우
- 굴리기 전에 위에 있었던 구슬을 위로 한 칸 옮겨줘야 한다.
- 위로 기울인 경우
- 굴리기 전에 아래 있었던 구슬을 아래로 한 칸 옮겨줘야 한다.
- 오른쪽으로 기울인 경우
- 굴리기 전에 왼쪽에 있었던 구슬을 왼쪽으로 한 칸 옮겨줘야 한다.
- 왼쪽으로 기울인 경우
- 굴리기 전에 오른쪽에 있었던 구슬을 오른쪽으로 한 칸 옮겨줘야 한다.
함수의 반환형으로는 두 공을 담는 pair을 사용하였다.
BFS 구현부가 가장 처리해야 할 것이 많았다.
queue<pair<struct ball, struct ball> > q;
q.push(make_pair(rb,bb));
while(!q.empty()){
pair<struct ball, struct ball> sit = q.front();
q.pop();
if(sit.first.time > 10){
cout << "-1";
return 0;
}
else{
bool redFlag = false;
bool blueFlag = false;
if(board[sit.first.y][sit.first.x] == 'O'){
redFlag = true;
}
if(board[sit.second.y][sit.second.x] == 'O'){
blueFlag = true;
}
if(redFlag && !blueFlag){
cout << sit.first.time;
return 0;
}
else if(!redFlag && !blueFlag){
for(int i=0;i<4;i++){
if(!(sit.first.pre_dir.first == -y_iter[i] && sit.first.pre_dir.second == -x_iter[i])){
pair<struct ball, struct ball> p;
p= (tilt(y_iter[i], x_iter[i], sit.first, sit.second));
if(!(p.first.y == sit.first.y && p.first.x == sit.first.x && p.second.y == sit.second.y && p.second.x == sit.second.x)){
q.push(p);
}
}
}
}
}
}
우선 bfs를 수행할 Queue를 선언해주는데, 두 개의 공을 함께 움직이기 위해서 Queue에는 두 개의 구슬을 pair로 담았다.
다음과 같이, 하나의 포지션에서는 최대 네 가지 경우의 수가 나올 수 있다. 그런데, 이 네 가지 경우를 빨간 구슬 파란 구슬 따로 bfs를 돌리게 되면 구현 난이도가 너무 높아지기 때문에, 저 상황 자체를 queue에 넣고 돌리기로 했다.
네 가지 방향으로 기울이는 부분의 구현은 다음과 같다.
for(int i=0;i<4;i++){
if(!(sit.first.pre_dir.first == -y_iter[i] &&
sit.first.pre_dir.second == -x_iter[i])){
pair<struct ball, struct ball> p;
p= (tilt(y_iter[i], x_iter[i], sit.first, sit.second));
if(!(p.first.y == sit.first.y && p.first.x == sit.first.x && p.second.y == sit.second.y && p.second.x == sit.second.x)){
q.push(p);
}
}
}
우선, 방금 전에 자신이 기울여졌던 방향으로는 다시 돌아가면 안된다. 따라서 구슬 구조체 안에 선언했던 pre_dir변수를 이용해 자신이 왔던 방향은 queue 에 담지 않도록 한다.
또, 기울였는데 움직이지 않은 경우에도 queue에 담지 않도록 한다.
이제 종료 조건을 잘 정해줘야 한다.
프로그램이 종료되는 경우는 다음의 경우이다.
- 10번을 초과해 기울인 경우
- 빨간 구슬이 구멍에 들어간 경우
- queue가 empty인 경우
이 세 개를 제외한 종료 조건은 없다.
처음에 제일 실수했던 것은 문제에서 실패의 경우로 소개한 사례를 모두 종료 조건으로 인식했다는 것이다.
예를 들어, 파란 구멍만 먼저 빠져버린 경우, 프로그램은 종료되지 않는다. 다른 경우의 수들이 아직 남아있기 때문이다. 문제에서 소개한 실패의 사례에 해당하는 경우 queue에 넣어주지 않는다. 결국은 조건을 만족하지 못해 기울인 횟수가 10번을 넘게 되기 때문에 자연스레 -1을 출력하며 실패하게 된다.
if(sit.first.time > 10){
cout << "-1";
return 0;
}
else{
bool redFlag = false;
bool blueFlag = false;
if(board[sit.first.y][sit.first.x] == 'O'){
redFlag = true;
}
if(board[sit.second.y][sit.second.x] == 'O'){
blueFlag = true;
}
if(redFlag && !blueFlag){
cout << sit.first.time;
return 0;
}
구슬이 구멍에 빠졌는지는 flag를 통해 알 수 있는데, 빨간 구슬만 구멍에 빠진 경우(redFlag) 종료되는 것을 볼 수 있다.
전체 코드는 다음과 같다.
#include <iostream>
#include <string>
#include <queue>
using namespace std;
char board[11][11];
int N, M;
struct ball{
int y, x, time;
char type;
pair<int,int> pre_dir;
};
bool isVisitedRed[11][11];
bool isVisitedBlue[11][11];
int answer = 0;
int timeLimit = 100;
int x_iter[4] = {1,0,-1,0};
int y_iter[4] = {0,1,0,-1};
struct ball rb;
struct ball bb;
pair<struct ball, struct ball> tilt(int y_dir,int x_dir,struct ball red, struct ball blue){
struct ball rB;
struct ball bB;
rB.y = red.y;
rB.x = red.x;
bB.y = blue.y;
bB.x = blue.x;
rB.time = red.time+1;
bB.time = blue.time+1;
rB.pre_dir.first = y_dir;
rB.pre_dir.second = x_dir;
bB.pre_dir.first = y_dir;
bB.pre_dir.second = x_dir;
//move red ball
while(1){
if(rB.y + y_dir >= 0 && rB.x + x_dir >=0 && rB.y + y_dir < N && rB.x + x_dir < M){
rB.y += y_dir;
rB.x += x_dir;
}
if(board[rB.y][rB.x] == '#'){
rB.y -= y_dir;
rB.x -= x_dir;
break;
}
if(board[rB.y][rB.x] == 'O'){
break;
}
}
// move blue ball
while(1){
if(bB.y + y_dir >= 0 && bB.x + x_dir >=0 && bB.y + y_dir < N && bB.x + x_dir < M){
bB.y += y_dir;
bB.x += x_dir;
}
if(board[bB.y][bB.x] == '#'){
bB.y -= y_dir;
bB.x -= x_dir;
break;
}
if(board[bB.y][bB.x] == 'O'){
break;
}
}
// when both balls are in same position
if(rB.y == bB.y && rB.x == bB.x && !(board[rB.y][rB.x] == 'O' && board[bB.y][bB.x]=='O')){
if(red.x == blue.x){
//down
if(y_dir == 1){
if(red.y < blue.y){
rB.y -= 1;
}
else {
bB.y -= 1;
}
}
else if(y_dir==-1){
if(red.y < blue.y){
bB.y++;
}
else {
rB.y++;
}
}
}
else if(red.y == blue.y){
if(x_dir==1){
if(red.x < blue.x){
rB.x--;
}
else{
bB.x--;
}
}
else if(x_dir==-1){
if(red.x < blue.x){
bB.x++;
}
else {
rB.x++;
}
}
}
}
return make_pair(rB,bB);
}
int main(){
cin >> N >> M;
for(int i=0;i<N;i++){
string tp;
cin >> tp;
for(int j=0;j<M;j++){
board[i][j] = tp[j];
if(tp[j] == 'R'){
rb.y = i;
rb.x = j;
rb.time = 0;
rb.type = 'R';
rb.pre_dir.first = 0;
rb.pre_dir.second = 0;
board[i][j] = '.';
}
if(tp[j] == 'B'){
bb.y = i;
bb.x = j;
bb.time = 0;
bb.type = 'B';
board[i][j]='.';
}
}
}
queue<pair<struct ball, struct ball> > q;
q.push(make_pair(rb,bb));
while(!q.empty()){
pair<struct ball, struct ball> sit = q.front();
q.pop();
if(sit.first.time > 10){
cout << "-1";
return 0;
}
else{
bool redFlag = false;
bool blueFlag = false;
if(board[sit.first.y][sit.first.x] == 'O'){
redFlag = true;
}
if(board[sit.second.y][sit.second.x] == 'O'){
blueFlag = true;
}
if(redFlag && !blueFlag){
cout << sit.first.time;
return 0;
}
else if(!redFlag && !blueFlag){
for(int i=0;i<4;i++){
if(!(sit.first.pre_dir.first == -y_iter[i] && sit.first.pre_dir.second == -x_iter[i])){
pair<struct ball, struct ball> p;
p= (tilt(y_iter[i], x_iter[i], sit.first, sit.second));
if(!(p.first.y == sit.first.y && p.first.x == sit.first.x && p.second.y == sit.second.y && p.second.x == sit.second.x)){
q.push(p);
}
}
}
}
}
}
cout << "-1";
return 0;
}
댓글남기기