삼성 SW 역량 테스트 기출 문제 : 구슬 탈출 2

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

13460번: 구슬 탈출 2

 

// 코드

import java.util.*;
import java.io.*;
import java.math.*;
 
public class Main{
  
  static int N, M;
  static char[][] map;
  
  static int[] dy = {-1, 1, 0, 0};
  static int[] dx = {0, 0, -1, 1};
  
  static boolean[][][][] visited;
  
  static class Ball {
    int[] Red;
    int[] Blue;
    int move;
    
    public Ball() { this.move = 0; }
    
    public Ball(Ball now) {
      this.Red  = now.Red;
      this.Blue = now.Blue;
      this.move = now.move;
    }
    
  }
  
  // main
  public static void main(String[] args) throws Exception {
    boolean isPossible = false;
    BufferedWriter bw  = new BufferedWriter(new OutputStreamWriter(System.out));
    BufferedReader br  = new BufferedReader(new InputStreamReader(System.in)); 
    StringTokenizer st = new StringTokenizer(br.readLine());
    StringBuilder sb   = new StringBuilder();
    
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    
    // '.' : 빈 칸
    // '#' : 벽
    // 'O' : 구멍의 위치
    // 'R' : 빨간 구슬의 위치
    // 'B' : 파란 구슬의 위치
    map = new char[N][M];
    Ball b = new Ball();
    
    for(int i=0; i<N; i++) {
      String str = br.readLine();
      for(int j=0; j<M; j++) {
        map[i][j] = str.charAt(j);
        if(map[i][j] == 'R') {
          b.Red = new int[]{i, j};
          map[i][j] = '.';
        } else if(map[i][j] == 'B') {
          b.Blue = new int[]{i, j};
          map[i][j] = '.';
        }
      }
    }
    
    visited = new boolean[N][M][N][M];
    Deque<Ball> deq = new ArrayDeque<>();
    deq.offer(b);
    visited[b.Red[0]][b.Red[1]][b.Blue[0]][b.Blue[1]] = true;
    
    while(!deq.isEmpty()) {
      
      Ball now = deq.pop();
      
      // 실패
      if(map[now.Blue[0]][now.Blue[1]] == 'O') continue;
      else if(now.move == 11) continue;
      
      // 성공
      if( map[now.Red[0]][now.Red[1]] == 'O' ) {
        sb.append(now.move + "\n");
        isPossible = true;
        break;
      }
      
      for(int i=0; i<4; i++) {
        Ball next = move(i, now);
        if(visited[next.Red[0]][next.Red[1]][next.Blue[0]][next.Blue[1]]) continue;
        
        visited[next.Red[0]][next.Red[1]][next.Blue[0]][next.Blue[1]] = true;
        deq.offer(next);
      }
    }
    
    if(isPossible) bw.write(sb.toString());
    else bw.write(String.valueOf(-1));
    
    br.close();
    bw.flush();
    bw.close();
  }
  
  static Ball move(int dir, Ball now) {
    
    Ball next = new Ball(now);
    int ny = 0, nx = 0;
    // 빨간공이 더 먼저 움직여야하는 상황이라면 true, 파란공이 먼저인 경우는 false
    boolean flag = false;
    
    switch(dir) { 
    // 상
    case 0:
      // 파란공이 더 위에 있다면 위에있는 파란공이 먼저 움직인다.
      if(next.Red[0] > next.Blue[0]) flag = false;
      // 빨간공이 더 위에 있다면 빨간공이 먼저 움직인다.
      else flag = true;
    break;
    
    // 하
    case 1:
      // 빨간공이 더 아래에 있다면 아래에 있는 빨간공이 먼저 움직인다.
      if(next.Red[0] > next.Blue[0]) flag = true;
      else flag = false;
    break;
    
    // 좌
    case 2:
      // 파란공이 더 왼쪽에 있으므로, 파란공이 먼저 움직인다.
      if(next.Red[1] > next.Blue[1]) flag = false;
      // 빨간공이 더 오른쪽에 있으므로, 빨간공이 먼저 움직인다.
      else flag = true;
    break;
    
    // 우
    case 3:
      // 빨간공이 더 오른쪽에 있으므로, 빨간공이 먼저 움직인다.
      if(next.Red[1] > next.Blue[1]) flag = true;
      // 파란공이 더 왼쪽에 있으므로, 파란공이 먼저 움직인다.
      else flag = false;
    break; 
    } // end of switch
    
    // 파란공이 먼저 움직이는 경우
    if(!flag) {
      // 파란공이 움직인다..
      ny = next.Blue[0] + dy[dir];
      nx = next.Blue[1] + dx[dir];
      
      while(map[ny][nx] == '.') {
        ny += dy[dir];
        nx += dx[dir];
      }
      
      if(map[ny][nx] == 'O') next.Blue = new int[] { ny, nx };
      else next.Blue = new int[] { (ny - dy[dir]), (nx - dx[dir]) };
      
      // 빨간공이 움직인다..
      ny = next.Red[0] + dy[dir];
      nx = next.Red[1] + dx[dir];
      
      while(map[ny][nx] == '.') {
        // 파란공과 위치가 겹치는 경우 탈출한다.
        if (ny == next.Blue[0] && nx == next.Blue[1]) break;
        
        ny += dy[dir];
        nx += dx[dir];
      }
      
      if(map[ny][nx] == 'O') next.Red = new int[] {ny, nx};
      else next.Red = new int[] { (ny - dy[dir]), (nx - dx[dir]) };
      
    }
    // 빨간공이 먼저 움직이는 경우
    else {
      // 빨간공이 움직인다..
      ny = next.Red[0] + dy[dir];
      nx = next.Red[1] + dx[dir];
      
      while(map[ny][nx] == '.') {
        ny += dy[dir];
        nx += dx[dir];
      }
      
      if(map[ny][nx] == 'O')  next.Red = new int[] { ny, nx };
      else next.Red = new int[] { (ny - dy[dir]), (nx - dx[dir]) };
      
      // 파란공이 움직인다..
      ny = next.Blue[0] + dy[dir];
      nx = next.Blue[1] + dx[dir];
      
      while(map[ny][nx] == '.') {
        // 빨간공과 위치가 겹치는 경우 탈출한다.
        if (ny == next.Red[0] && nx == next.Red[1]) break;
        
        ny += dy[dir];
        nx += dx[dir];
      }
      
      if(map[ny][nx] == 'O')  next.Blue = new int[] { ny, nx };
      else next.Blue = new int[] { (ny - dy[dir]), (nx - dx[dir]) };
    }
    
    next.move++;
    return next;
  }
  
}