[백준] 13460번 구슬 탈출2

13460번 구슬 탈출2

---

1. 이해하기

   • 빨간 구슬과 파란 구슬이 보드를 움직일 때마다 동시에 움직인다.

   • 빨간 구슬만 구멍에 빠져야 한다. 파란 구슬이 동시에 빠지는 경우는 실패한 경우로 생각한다.

   • 성공한 경우에 구슬을 최소로 움직인 경우를 구한다.

     ---

2. 구현하기

   • 빨간 구슬과 파란 구슬이 동시에 움직이는 것

     Point move(Point ball, int dir) {
         int nx = ball.x+dx[dir], ny = ball.y+dy[dir];
         while(1) {
             if(map[nx][ny] == '#') {
                 return {nx-dx[dir],ny-dy[dir]};
             } else if(map[nx][ny] == 'O') {
                 return {-1,-1};
             }
             nx += dx[dir]; ny += dy[dir];
         }
     }

   • 구슬이 구멍에 빠졌는지 체크

     bool is_in_hole(Point ball) {
         return ball.x == -1;
     }

   • 성공한 경우에 구슬이 최소로 움직이는 경우를 구하는 완전탐색

     int solve(Point red, Point blue, int cnt) {
         if(cnt == 11) return MAX;
         if(blue.x == -1) return MAX;
         if(red.x == -1) return cnt;
     
         int ret = MAX;
         for(int i = 0; i < 4; i++) {
             Point n_red = move(red,i), n_blue = move(blue,i);
             if(n_red.x == n_blue.x and n_red.y == n_blue.y and (!is_in_hole(n_red) and !is_in_hole(n_blue))) {
                 if(i == 0) {
                     if(red.y > blue.y) {
                         n_blue.y -= 1;
                     } else {
                         n_red.y -= 1;
                     }
                 } else if(i == 1) {
                     if(red.y < blue.y) {
                         n_blue.y += 1;
                     } else {
                         n_red.y += 1;
                     }
                 } else if(i == 2) {
                     if(red.x > blue.x) {
                         n_blue.x -= 1;
                     } else {
                         n_red.x -= 1;
                     }
                 } else if(i == 3) {
                     if(red.x < blue.x) {
                         n_blue.x += 1;
                     } else {
                         n_red.x += 1;
                     }
                 }
             }
             ret = min(ret,solve(n_red,n_blue,cnt+1));
         }
         return ret;
     }

   ---

3. 전체 코드

   #include <iostream>
   using namespace std;
   struct Point {
       int x,y;
   };
   const int MAX = 987654321;
   string map[10];
   int dx[] = {0,0,1,-1};
   int dy[] = {1,-1,0,0};
   Point red,blue;
   
   Point move(Point ball, int dir) {
       int nx = ball.x+dx[dir], ny = ball.y+dy[dir];
       while(1) {
           if(map[nx][ny] == '#') {
               return {nx-dx[dir],ny-dy[dir]};
           } else if(map[nx][ny] == 'O') {
               return {-1,-1};
           }
           nx += dx[dir]; ny += dy[dir];
       }
   }
   
   bool is_in_hole(Point ball) {
       return ball.x == -1;
   }
   
   int solve(Point red, Point blue, int cnt) {
       if(cnt == 11) return MAX;
       if(blue.x == -1) return MAX;
       if(red.x == -1) return cnt;
   
       int ret = MAX;
       for(int i = 0; i < 4; i++) {
           Point n_red = move(red,i), n_blue = move(blue,i);
           if(n_red.x == n_blue.x and n_red.y == n_blue.y and (!is_in_hole(n_red) and !is_in_hole(n_blue))) {
               if(i == 0) {
                   if(red.y > blue.y) {
                       n_blue.y -= 1;
                   } else {
                       n_red.y -= 1;
                   }
               } else if(i == 1) {
                   if(red.y < blue.y) {
                       n_blue.y += 1;
                   } else {
                       n_red.y += 1;
                   }
               } else if(i == 2) {
                   if(red.x > blue.x) {
                       n_blue.x -= 1;
                   } else {
                       n_red.x -= 1;
                   }
               } else if(i == 3) {
                   if(red.x < blue.x) {
                       n_blue.x += 1;
                   } else {
                       n_red.x += 1;
                   }
               }
           }
           ret = min(ret,solve(n_red,n_blue,cnt+1));
       }
       return ret;
   }
   
   int main() {
       int N,M;
       cin >> N >> M;
       for(int i = 0; i < N; i++) {
           cin >> map[i];
       }
       for(int i = 0; i < N; i++) {
           for(int j = 0; j < M; j++) {
               if(map[i][j] == 'R') red = {i,j};
               else if(map[i][j] == 'B') blue = {i,j};
           }
       }
   
       int ans = solve(red,blue,0);
       if(ans == MAX) cout << -1 << '\n';
       else cout << ans << '\n';
   
       return 0;
   }