문제

문제 링크

어떻게 접근할 것인가

  • 이 문제는 BFS를 이용해서 풀 수 있다. 큐에 들어가는 정보는 두 구슬의 좌표와 이동한 횟수이다.
  • 매번 두 구슬은 벽을 만날 때까지 이동시키고 앞서 있는 구슬이 벽에 붙어있는 구슬이 될 것이기 떄문에 이동 후 두 구슬의 좌표가 같다면 이전 위치에서 덜 움직인 구슬을 하나 뒤로 이동시킨다.
  • 파란구슬이 도착점에 도착하면 continue하고 빨간구슬이 도착점에 들어가면 cnt + 1을 출력한다.
  • 이동 후의 두 구슬 중에 하나라도 좌표가 바뀌면 넣어준다.
  • 이동 횟수는 최대 10번이기 때문에 cnt가 10이 넘어가면 패쓰한다.

코드

#include <cstdio>
#include <queue>
using namespace std;

typedef struct info{
    int rx, ry, bx, by, cnt;
    info(int i, int j, int k, int l, int m){
        rx = i, ry = j, bx = k, by = l, cnt = m;
    }
    info();
}info;

int n, m, board[11][11], rx, ry, bx, by;
int d[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
int main(){
    queue<info> q; 
    scanf("%d %d ", &n, &m);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            char temp;
            scanf("%c", &temp);
            if(temp == '.' || temp == 'B' || temp == 'R') board[i][j] = 0;
            else if(temp == 'O')board[i][j] = -2;
            else board[i][j] = -1;
            if(temp == 'B')bx = j, by = i;
            else if(temp == 'R')rx = j, ry = i;
        }
        getchar();
    }

    board[ry][rx] = 1;
    q.push(info(rx, ry, bx, by, 0));
    while(!q.empty()){
        info front = q.front(); q.pop();
        int frx = front.rx, fry = front.ry, fbx = front.bx, fby = front.by, cnt = front.cnt; 
        if(cnt >= 10) continue;
        for(int i = 0; i < 4; i++){
            int end = 0, cnt_r = 0, cnt_b = 0;
            int nrx = frx, nry = fry, nbx = fbx, nby = fby;
            while(board[nby + d[i][0]][nbx + d[i][1]]!= -1){
                nbx += d[i][1], nby += d[i][0];
                cnt_b ++;
                if(board[nby][nbx] == -2){
                    end -= 2;
                    break;
                }
            }
            if(end < 0) continue;
            while(board[nry + d[i][0]][nrx + d[i][1]]!= -1){
                nrx += d[i][1], nry += d[i][0];
                cnt_r ++;
                if(board[nry][nrx] == -2){
                    end ++;
                    break;
                }
            }
            if(nrx == nbx && nry == nby){
                if(cnt_r < cnt_b)nbx -= d[i][1], nby -= d[i][0];
                else nrx -= d[i][1], nry -= d[i][0];
            }
            if(end){
                if(cnt > 10) printf("-1");
                else printf("%d", cnt + 1);
                return 0;
            }
            q.push(info(nrx, nry, nbx, nby, cnt + 1));
        }
    }
    printf("-1");    
}

느낀점

  • 삼성 문제라 긴장하면서 풀었는데 푸는데 한시간 반이 걸렸다.
  • 물론 방법을 생각해내는데도 시간이 걸렸지만 예외 케이스를 처리해주는데 더 많은 시간이 소요되었다.
  • 풀었다는 사실에 만족한다. 다른 문제도 열심히 풀어봐야겠다.