백준 13459번, 13460번, 15644번, 15653번 : 구슬 탈출 1~4 풀이

1. 문제 링크

• 구슬 탈출 : https://www.acmicpc.net/problem/13459
• 구슬 탈출 2 : https://www.acmicpc.net/problem/13460
• 구슬 탈출 3 : https://www.acmicpc.net/problem/15644
• 구슬 탈출 4 : https://www.acmicpc.net/problem/15653

 

---

2. 풀이 방법

이 문제를 처음 읽었을 때 확실한 방법과 코드가 떠오르지 않아서 다소 당황스러웠다.

최근에 감을 조금 잃어버린 탓인지.. 오랜만에 감 잡기에 굉장히 좋은 문제라고 느꼈다.

 

우선 초기 상태에서 상하좌우 4방향으로 구슬을 굴리면서 가능한 경우를 모두 탐색해야 한다.

빨간 구슬이 구멍에 빠지는 경우가 나올 때까지 모든 경우를 탐색해야 한다.

 

그리고 이미 탐색한 경우를 다시 탐색하지 않기 위해서는 방문 처리가 필요하다.

여기서 빨간 구슬의 x 좌표와 y 좌표, 파란 구슬의 x 좌표와 y 좌표로 방문 처리를 하도록 4차원 배열을 이용한다는 점이 첫 번째로 인상 깊은 부분이었다.

bool visited[10][10][10][10];

 

비슷하게 BFS 큐에서 탐색한 경우를 저장할 때에도 빨간 구슬의 좌표와 파란 구슬의 좌표를 함께 저장하여 각 경우를 관리했다.

struct Balls{
    int rx, ry, bx, by;

    Balls() {
    }

    Balls(int rx, int ry, int bx, int by) : rx(rx), ry(ry), bx(bx), by(by) {
    }
};

 

구슬 탈출 1, 2, 3의 경우에는 최대 10번까지만 이동할 수 있으므로 BFS 탐색을 진행할 때 이동 횟수로 구분지어주어서 10번 이동하는 경우까지만 탐색해주었다.

queue<Balls> bfs_que;

for (int depth = 1; depth <= 10; depth++) {
    int bfs_iter = size(bfs_que);

    while (bfs_iter-- > 0) {
        Balls cur = bfs_que.front();
        bfs_que.pop();

        // ...
    }
}

 

또는 Balls 에 이동한 횟수도 함께 저장해서 관리해도 된다.

구슬 탈출 4 문제에서는 이동 횟수 제한이 없으므로 이렇게 구현하긴 했다.

struct Balls{
    int rx, ry, bx, by;
    int cnt = 0;

    Balls() {
    }

    Balls(int rx, int ry, int bx, int by) : rx(rx), ry(ry), bx(bx), by(by) {
    }
};

queue<Balls> bfs_que;

while (!bfs_que.empty()) {
    Balls cur = bfs_que.front();
    bfs_que.pop();

    // ...
}

 

큐에서 하나의 경우를 꺼낸 후에는 상하좌우 4방향으로 각각 탐색을 진행해주었다.

우선 선택한 방향으로 벽 또는 구슬을 만날 때까지 빨간 구슬과 파란 구슬을 각각 굴렸다.

빨간 구슬을 굴리는 과정과 파란 구슬을 굴리는 과정은 로직이 비슷하므로, 공통 로직을 move 함수로 따로 분리해주었다.

int move(int x, int y, int d) {
    int moved = 1;
    int nx = x + dx[d];
    int ny = y + dy[d];

    while (board[nx][ny] == '.') {
        moved++;
        nx += dx[d];
        ny += dy[d];
    }

    if (board[nx][ny] == 'O') {
        return moved;
    }

    return moved - 1;
}

 

위의 move 함수를 구현할 때 움직인 거리를 반환하도록 했다.

이렇게 한 이유는 두 구슬을 끝까지 밀었을 때 두 구슬의 위치가 겹치는 결과가 나올 수도 있는데, 문제에서 두 구슬은 겹칠 수 없다고 했기 때문이다.

따라서 두 구슬의 위치가 겹치는 결과가 나온다면 더 많이 움직인 구슬을 한 칸 뒤로 되돌려놓아야 하고, 그러려면 각 구슬이 움직인 거리를 비교해야 하므로 움직인 거리를 반환하도록 구현한 것이다.

바로 이 부분이 문제를 풀면서 두 번째로 인상 깊은 부분이었다.

// 빨간 구슬과 파란 구슬은 같은 칸에 위치할 수 없으므로 더 먼 거리를 이동한 구슬을 한 칸 뒤로 이동시킨다.
if (nxt.rx == nxt.bx && nxt.ry == nxt.by) {
    if (red_moved > blue_moved) {
        nxt.rx -= dx[d];
        nxt.ry -= dy[d];
    }
    else {
        nxt.bx -= dx[d];
        nxt.by -= dy[d];
    }
}

 

그리고 두 구슬을 움직였는데 파란 구슬이 구멍에 들어간 경우, 해당 탐색은 더 이상 수행하지 않고 다른 경우를 탐색하도록 했다.

또한 빨간 구슬이 구멍에 들어간 경우에는 이 경우가 곧 답이 되므로 탐색을 즉시 종료하도록 했다.

// 파란 구슬이 구멍에 들어가면 더 이상 탐색하지 않는다.
if (board[nxt.bx][nxt.by] == 'O') {
    continue;

// 빨간 구슬이 구멍에 들어가면 그때의 횟수를 답에 저장하고 탐색을 종료한다.
if (board[nxt.rx][nxt.ry] == 'O') {
    ans = nxt.cnt;
    break;
}

 

---

3. 전체 코드 (C++ & Java)

• 백준 13459번 구슬 탈출
  • C++ : https://github.com/infikei/algorithm/blob/main/baekjoon_all/13000%2B/boj_13459.cpp
  • Java : https://github.com/infikei/algorithm/blob/main/baekjoon_all/13000%2B/boj_13459.java
• 백준 13460번 구슬 탈출 2
  • C++ : https://github.com/infikei/algorithm/blob/main/baekjoon_all/13000%2B/boj_13460.cpp
  • Java : https://github.com/infikei/algorithm/blob/main/baekjoon_all/13000%2B/boj_13460.java
• 백준 15644번 구슬 탈출 3
  • C++ : https://github.com/infikei/algorithm/blob/main/baekjoon_all/15000%2B/boj_15644.cpp
• 백준 15653번 구슬 탈출 4
  • C++ : https://github.com/infikei/algorithm/blob/main/baekjoon_all/15000%2B/boj_15653.cpp