[백준] 13640번 구슬 탈출 2

https://www.acmicpc.net/problem/13460

삼성sw 역량 테스트 기출 문제답게 쉽지 않다. 이 문제는 DFS 문제(BFS로도 가능)이다.

1. 다른 DFS 문제와 다른 점이 있다면 해당 문제는 공이 벽을 만날 때까지 한 방향으로 움직인다는 점이다. 벽을 만나게 되면 해당 공의 움직임은 멈추게 된다.
2. 다른 DFS 문제와 다르게 공이 방문한 위치를 생각할 필요가 없다.(방문을 여러번해도 된다.) 몇 번 기울였는지가 DFS의 종료 조건이 된다.
3. 빨간 공과 파란 공의 위치에 따라 무슨 공을 먼저 움직일지 생각을 해야한다.

나는 문제를 풀면서 이 정도가 문제를 푸는 조건이라고 생각했다.

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int arr[10][10] = {0, };
pair<int, int> hole;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

// 0 is right 1 is down, 2 is left, 3 is up.

bool sameball(pair<int, int> ball, pair<int, int> newball){
    if(ball.first == newball.first && ball.second == newball.second)
        return true;
    return false;
}

int whichfirst(pair<int, int> red, pair<int, int> blue, int dir){
    int ret = 0;
    if(dir == 0){
        if(blue.second > red.second)
            ret = 1;
    }
    else if(dir == 1){
        if(blue.first > red.first)
            ret = 1;
    }
    else if(dir == 2){
        if(blue.second < red.second)
            ret = 1;
    }
    else{
        if(blue.first < red.first)
            ret = 1;
    }
    return ret;
}// 0 is red first, 1 is blue first

pair<int, int> dirball(pair<int, int> ball, int ballnum, int dir){
    int x, y;
    x = ball.first;
    y = ball.second;
    arr[x][y] = 0;
    while(arr[x+dx[dir]][y+dy[dir]] == 0){
        x += dx[dir];
        y += dy[dir];
    }
    arr[x][y] = ballnum;
    if(arr[x+dx[dir]][y+dy[dir]] == 3){
        arr[x][y] = 0;
        x += dx[dir];
        y += dy[dir];
    }
    ball = make_pair(x, y);
    return ball;
}

int DFS(pair<int, int> red, pair<int, int> blue, int num){
    if(num > 10)
        return -1;
    if(blue.first == hole.first && blue.second == hole.second)
        return -1;
    else if(red.first == hole.first && red.second == hole.second){
        return num;
    }
    int ret = -1;
    int a = -1;
    pair<int, int> newred, newblue;
    for(int i = 0; i<4; i++){
        if(whichfirst(red, blue, i) == 0){
            newred = dirball(red, 1, i);
            newblue = dirball(blue, 2, i);
        }
        else{
            newblue = dirball(blue, 2, i);
            newred = dirball(red, 1, i);
        }
        //printf("%d %d %d %d\n", red.first, red.second, blue.first, blue.second);
        
        if(!sameball(red, newred) || !sameball(blue, newblue))
            a = DFS(newred, newblue, num+1);

        arr[newred.first][newred.second] = 0;
        arr[newblue.first][newblue.second] = 0;
        arr[red.first][red.second] = 1;
        arr[blue.first][blue.second] = 2;
        arr[hole.first][hole.second] = 3;

        if(ret == -1)
            ret = a;
        else if(a != -1){
            ret = min(ret, a);
        }
    }
    return ret;
}

int main(int argc, const char * argv[]) {
    int N, M, ans;
    char c;
    pair<int, int> r, b;
    scanf("%d %d", &N, &M);
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            scanf(" %c", &c);
            if(c == '#'){
                arr[i][j] = -1;
            }
            else if(c == '.'){
                arr[i][j] = 0;
            }
            else if(c == 'R'){
                arr[i][j] = 1;
                r = make_pair(i, j);
            }
            else if(c == 'B'){
                arr[i][j] = 2;
                b = make_pair(i, j);
            }
            else if(c == 'O'){
                arr[i][j] = 3;
                hole = make_pair(i, j);
            }
        }
    }
    ans = DFS(r, b, 0);
    printf("%d\n", ans);
    return 0;
}

1. 우선 main함수를 보자. main함수에서는 문자열을 받고, 각 문자열에 대해서 숫자를 부여했다. -1은 '#', 0은 '.', 1은 'R', 2는 'B', 3은 'O'(hole)이다. R,B,O의 경우 공의 위치를 pair을 이용해 x와 y로 남겨두었다.

2. 다음으로 DFS 함수를 보자. DFS의 경우 리턴조건을 num이 10이상(기울인 횟수), blue가 hole의 위치가 일치할 때 -1을 출력하도록 했고, red와 hole의 위치가 일치할 때 num을 리턴하도록 하였다. blue가 hole에 들어갔을 때 -1을 먼저 리턴을 해, red와 blue가 hole에 동시에 들어가는 경우에도 -1을 리턴하도록 만들었다. newred와 newblue의 경우, 공을 옮겼을 때(dirball 함수)의 위치를 말한다. 하지만 공을 옮기기 위해서는 무슨 공을 먼저 옮길 건지(whichfirst 함수)를 먼저 구한 다음 공을 옮겨야 한다. 공을 옮긴 후, DFS함수를 통해 재귀를 하고 재귀한 후에는 다시 그 공의 위치를 본래의 위치대로 옮기게 된다. 만약 ret값이 -1이라면 DFS에서 구한 값(a)을 ret에 넣게 되고, 그렇지 않다면 ret값과 DFS에서 구한 값 중 작은 값을 ret에 넣게 되고, 해당 값을 리턴하게 된다.

3. dirball 함수를 보자. 해당 함수는 공의 위치(pair), 공의 색깔(1;빨간색, 2;파란색), 공의 방향(0;오른쪽(+), 1;아래쪽(+), 2;왼쪽(-), 3;위쪽(-))을 차례대로 받는다. 해당 공의 위치는 공의 방향에 따라서 다음 위치가 0일때 계속 이동하게 된다. 만약 이외의 숫자를 만나게 되면 공이 멈추고 arr배열에 해당 공의 넘버가 붙게 된다. 하지만, 다음 공의 위치가 3(hole)일 경우 해당 위치의 좌표를 남기게 되고 이전의 공이 위치한 곳의 값은 0이 된다. 공이 구멍에 빠진 것이다.

4. whichfirst의 함수의 경우 빨간색 공과 파란색 공의 위치(pair), 그리고 기울인 방향을 받는다. 일반적으로 빨간색 공이 먼저 움직이는 것으로 가정을 한다. 하지만, 특정 조건일 때 파란색 공이 먼저 움직이도록 했다.

• 오른쪽일 때(dir == 0), 파란색의 y좌표가 빨간색의 y좌표보다 클 때
• 아래쪽일 때(dir == 1), 파란색의 x좌표가 빨간색의 x좌표보다 클 때
• 왼쪽일 떄(dir == 2), 파란색의 y좌표가 빨간색의 y좌표보다 작을 때
• 위쪽일 때(dir ==3), 파란색의 x좌표가 빨간색의 x좌표보다 작을 떄

해당 조건일 때 파란색이 먼저 움직여야 해 1을 리턴하도록 했다. 그러나 그 외의 조건일 때는 0을 리턴하도록 했다.

5. sameball 함수를 보자. 해당 함수는 없어도 될 거 같은 느낌적인 느낌인데, 내가 이 함수를 넣은 이유는 공을 기울여도 움직이지 않는 경우가 있기 때문이다. 이 경우 오히려 계산량을 잡아먹기만 할 뿐 실질적으로 도움이 되지 않기 때문에 움직이기 전의 공과 움직이고 난 후의 공을 비교해 좌표가 같다면 true를 리턴하도록 만들었다. 그래서 DFS함수에서 두 공 모두 움직이지 않았다면 DFS를 재귀하지 못하도록 만들었다.

6. 이 문제의 경우 많은 반례에 직면하게 된다. 나같은 경우 반례의 문제보단 오타로 인해서 답을 못 맞췄던 것이지만, 해당 문제의 반례를 구글링하게 된다면 수 많은 반례들이 있다는 것을 알 수 있다. 그래서 나는 조금 도움 될 만한 반례를 몇개 적어놓도록 하겠다.

10 10
##########
#R#...#..#
#...#....#
#######.##
#....#..##
#.####O#B#
#.#.....##
#........#
#....#...#
##########
// ans = -1

5 10
##########
#.#......#
##.......#
#OR..B.#.#
##########
//ans = 7

보통 제출했을 때 오류가 기울인 횟수를 생각을 하지 못했다던지, 무슨 공을 먼저 옮겨야하는지 생각을 하지 못했다던지, 공을 옮기는 알고리즘이 잘못되었던지 인 것 같다. 물론 나처럼 오타로 인해서 틀렸을 수도 있다. 나는 sameball에서 first는 first끼리, second는 second끼리 비교해야 했었는데 first와 second를 비교하는 참사를 일으켜 1시간 동안 해당 문제를 잡고 있었다.
이 글을 읽는 다른 분들은 나처럼 오타를 안 일으키셨으면 좋겠다.