구슬 탈출 2

문제: 구슬 탈출 2 (백준 13460번)

구조 분석

해당 문제를 처음 봤을 때 매우 당황스러웠다. 겉보기에는 이전에 풀어봤던 연구소 (백준 14502번) 문제와 매우 유사했다. 이전에 풀었던 연구소 문제는 map이 주어지고 바이러스가 퍼져나가는 조건이어서 보자마자 bfs를 이용해야 한다는 생각을 했다. 그런데 이 문제의 경우 bfs를 이용해야 한다는 것을 바로 알아채지 못했다. 그래서 bfs를 써야지 하는 한가지 기준을 만들었다.

몇 번, 몇 단계, 몇 시간 

다음의 키워드가 있는 경우 tree의 depth나 level을 체크해야 하므로 bfs나 dfs를 써야하는 확률이 높다. 그리고 일반적인 경우 bfs를 더 쓰는 것 같다. 왜냐하면 bfs는 optimal 하고 dfs는 optimal하지 않기 때문이다. 그러나 문제의 조건에 따라 그리고 메모리 사용량의 제한에 따라 dfs를 사용하는 경우도 있을 것이다.

그럼 bfs를 사용하기로 결정한 다음 무엇을 해야 할까? 바로 각 노드에 무엇을 저장할 지 생각해야 한다. 대게 map 문제의 경우 각 노드를 구조체 형식으로 좌표를 저장하는 문제가 많다. 연구소 문제에서도 바이러스가 퍼져나가는 조건 때문에 map 자체를 저장해야 하는지 고민했었는데 map 자체를 저장하는 경우 메모리 소모가 크기 때문에 일반적으로 좌표를 저장한다. 해당 문제에서도 빨간 구슬의 좌표와 파란 구슬의 좌표를 저장해서 풀이했다.

풀이 방법

해당 문제와 같이 map이 주어지고 bfs를 이용해 탐색을 해야하는 문제의 경우 우선 입력받는 코드와 bfs 함수 코드를 먼저 만들자. 이제 bfs구조는 매우 익숙하니까 문제에서 구슬의 이동을 생각하면서 구슬이 움직이는 힘수를 만드는 것보다 bfs 틀을 짜는 것이 더 빠르고 효율적이다. 아래의 코드는 구조 틀 예시이다.

void bfs() {
    while(!Q.empty()) {
        // Q 맨 앞의 노드 정보 불러오기
        int x = Q.front().x;
        int y = Q.front().y;
        // Q 맨 앞의 노드 pop
        Q.pop();
        // break 조건 (있을 경우)  
        // 노드 expand
    }
}

해당 틀을 먼저 만들어 놓고 나머지를 함수나 조건을 채우면 더 구조를 파악하기 쉽다.

이 다음으로는 map 문제에서 빠질 수 없는 코드를 작성한다.

int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

void bfs() {
    while(!Q.empty()) {
        // Q 맨 앞의 노드 정보 불러오기
        int x = Q.front().x;
        int y = Q.front().y;
        // Q 맨 앞의 노드 pop
        Q.pop();
        for (int i=0; i<4; i++) {
            // 다음 좌표 설정
            int nx = x + dx[i];
            int ny = y + dy[i];
            // map에서 nx, ny에 대해 expand 실시
        }
    }
}

이와 같이 모든 map 문제에 공통으로 적용되는 틀을 만들고 이 다음에 각 조건에 맞게 expand를 실시하면 된다.

해당문제에서는 expand 과정이 매우 까다로웠으며 이를 간략하게 정리하려고 한다.
우선 구슬이 두 개 있는 경우이기 때문에 두 개의 구슬 움직임을 동시에 생각하면 조건이 매우 많아지고 문제는 더 까다로워진다. 따라서 구슬의 움직임을 하나씩 분리하여 생각해야 한다.

for (int i=0; i<4; i++) {
    // next position of beads
    int nrx = crx;
    int nry = cry;
    int nbx = cbx;
    int nby = cby;
    // counter to check distance of the beads move
    int rc = 0;
    int bc = 0;
    int c = cnt+1;
    // move read beads
    while(1) {
        if (board[nrx+dx[i]][nry+dy[i]]!='#' && board[nrx][nry]!='O') {
            nrx += dx[i];
            nry += dy[i];
            rc++;
        }
        else {
            break;
        }
    }
    // move blue beads
    while(1) {
        if (board[nbx+dx[i]][nby+dy[i]]!='#' && board[nbx][nby]!='O') {
            nbx += dx[i];
            nby += dy[i];
            bc++;
        }
        else {
            break;
        }
    }  
}

이후 각 구슬에 대해서 goal 여부를 확인하고 두 구슬이 겹치는 경우에 대해서 추가로 확인하는 코드를 작성하면 된다. 그리고 끝으로 visited 여부를 확인하고 조건이 다 성립한다면 queue에 넣어주면 된다.

코드

#include <stdio.h>
#include <iostream>
#include <string>
#include <queue>
using namespace std;

int n, m;
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
char board[10][10];
int visited[10][10][10][10] = {0,};
typedef struct bead {
    int rx, ry;
    int bx, by;
    int cnt;
} Bead;
queue<Bead> Q;

void bfs() {
    while(!Q.empty()) {
        // current position of beads
        int crx = Q.front().rx;
        int cry = Q.front().ry;
        int cbx = Q.front().bx;
        int cby = Q.front().by;
        int cnt = Q.front().cnt;
        Q.pop();
        if (cnt >= 10) break;
        for (int i=0; i<4; i++) {
            // next position of beads
            int nrx = crx;
            int nry = cry;
            int nbx = cbx;
            int nby = cby;
            // counter to check distance of the beads move
            int rc = 0;
            int bc = 0;
            int c = cnt+1;
            // move read beads
            while(1) {
                if (board[nrx+dx[i]][nry+dy[i]]!='#' && board[nrx][nry]!='O') {
                    nrx += dx[i];
                    nry += dy[i];
                    rc++;
                }
                else {
                    break;
                }
            }
            // move blue beads
            while(1) {
                if (board[nbx+dx[i]][nby+dy[i]]!='#' && board[nbx][nby]!='O') {
                    nbx += dx[i];
                    nby += dy[i];
                    bc++;
                }
                else {
                    break;
                }
            }
            if (board[nbx][nby] == 'O') continue;
            if (board[nrx][nry] == 'O') {
                cout << c << "\n";
                return;
            }
            // case: beads are in same position
            if (nrx == nbx && nry == nby) {
                if (rc > bc) {
                    // case: read bead is behind blue bead
                    nrx -= dx[i];
                    nry -= dy[i];
                }
                else {
                    // case: blue bead is behind read bead
                    nbx -= dx[i];
                    nby -= dy[i];
                }
            }
            if (visited[nrx][nry][nbx][nby]==1) {
                continue;
            }
            visited[nrx][nry][nbx][nby] = 1;
            Q.push({nrx,nry,nbx,nby,c});
        }
    }
    cout << -1 << "\n";
}

int main() {
    string str;
    cin >> n >> m;
    int r_x,r_y,b_x,b_y;
    for (int i=0; i<n; i++) {
        cin >> str;
        for (int j=0; j<m; j++) {
            board[i][j] = str[j];
            if (str[j] == 'R') {
                r_x = i;
                r_y = j;
            }
            else if (str[j] == 'B') {
                b_x = i;
                b_y = j;
            }
        }
    }
    Q.push({r_x,r_y,b_x,b_y,0});
    visited[r_x][r_y][b_x][b_y] = 1;
    bfs();
    return 0;
}

정리

if (board[nrx+dx[i]][nry+dy[i]]!='#' && board[nrx][nry]!='O')
if (board[nbx+dx[i]][nby+dy[i]]!='#' && board[nbx][nby]!='O')  

해당 부분 떄문에 삽질을 엄청 했다. map 문제의 경우 이런 조건 같은 경우에서 코너 케이스에 걸리는 경우가 많아서 더 어려운 것 같다. 이런 부분은 문제를 많이 풀면서 이런 디테일을 잡는 것을 연습해야겠다.