[백준] #13460. 구슬 탈출 2

MTTW·2021년 4월 14일

BFS C baekjoon ps 백준 자료구조

Problem Solving

목록 보기

6/11

문제는 여기서 확인할 수 있다. BaekJoon #13460. 구슬 탈출 2

📌 POINT

보드를 기울였을 때 빨간 구슬'만' 도착지에 도착하는가
10번의 시도 안에 성공한다면 몇 번만에 도착하는가
👉 이동 + 횟수 = BFS 알고리즘
주의할 점
- 조건 : Red, Blue는 같은 칸에 위치할 수 없다.
Red, Blue 공이 같은 line 상에 존재했고 굴린 결과 위치가 같아진다면 후 처리 필요
- 경로 중 도착지가 있는지 확인 필요

🚀 풀이

Ready

Red, Blue 공의 위치 정보가 항상 묶여 다닐 예정. 가독성을 위해서라도 위치 정보를 담을 구조체를 미리 준비한다.

struct pos{
    int x;
    int y;
    pos(int X, int Y) : x(X), y(Y) {}
};

지도, 보드 같은 경우에는 각 칸의 상태를 미리 숫자로 바꿔서 처리한다.(많은 경우 문자열 비교가 더 성가셨다.) 그리고 숫자로 바꾼 상태는 보기 쉽게 #define 해준다.

#define WALL -1
#define BLANK 0
#define HOLE 1

GO

1. 기본적인 BFS 틀을 만들어준다.

1.1. game_on 함수는 시작 시 공의 위치를 받아서 성공한다면 시도한 횟수를, 10번 이내 성공하지 못하면 -1을 리턴한다.

1.2. day별로 움직인 결과 red, blue의 위치 정보쌍을 큐에 담는다.

int game_on(pos start_red, pos start_blue){
    queue<pair<pos, pos>> q;
    q.push(make_pair(start_red, start_blue));

    int day = 1;
    bool hole_in = false;
    for(; day<=10; day++){
        int qsize = q.size();
        for(int i=0; i<qsize; i++){
            // tilt
            pos red = q.front().first;
            pos blue = q.front().second;
            q.pop();

            hole_in = tilt_board(red, blue, q);
            if(hole_in) return day;
        }
    }
    return -1;
}

2. 사방으로 이동

2.1. 이동 결과 목적지 도착 여부를 bool 타입으로 받는다.
2.2. red, blue 둘 다 도착하지 않았다면 큐에 담겨서 돌아온다.

bool tilt_board(pos &red, pos &blue, queue<pair<pos, pos>> &q){
    if(tilt_left(red, blue, q)) return true;
    if(tilt_right(red, blue, q)) return true;
    if(tilt_up(red, blue, q)) return true;
    if(tilt_down(red, blue, q)) return true;
    return false;
}

3. 기울인 결과 저장

위 코드에서 봤듯이 위 아래 좌 우 함수를 따로 만들었다. 뭔가 합칠 수 있을 것 같지만... 일단 모르겠으니 아는 방법으로 작성했다.

3.1. 이동하고 도착 여부 조사

is_red_in = move(next_red, move_dir[0]);
is_blue_in = move(next_blue, move_dir[0]);

3.2. 같은 라인에 두 공이 존재했는지 > 이동 후에 겹쳐졌는지

// 같은 라인 상에 존재하는지
// right (방향에 따라 코드 차이 발생)
if(red.x == blue.x){
    if(next_red.y == next_blue.y){
        if(red.y < blue.y) next_red.y--;
        else next_blue.y--;
    }
}

3.3. 도착 여부 리턴

if(is_red_in && !is_blue_in) return true;
else if(!is_blue_in){
    q.push(make_pair(next_red, next_blue));
}
return false

4. 보드를 기울였을 때 공 움직이기

move_dir 배열을 사용하면 코드가 한결 깔-끔

// right, left, down, up
int move_dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

bool move(pos &ball, int dir[]){
    while(true){
        pos next = ball;
        next.x += dir[0];
        next.y += dir[1];
        if(board[next.x][next.y] == HOLE){
            return true;
        }
        else if(board[next.x][next.y] == BLANK){
            ball = next;
        }
        else {  // WALL
            return false;
        }
    }
}