[백준][java] 구슬 탈출 2

import java.io.FileInputStream;
import java.util.Scanner;

public class 구슬_탈출_2 {

    private static int N, M;
    private static char[][] board;
    private static int answer = Integer.MAX_VALUE;
    private static int[] di = { 0, 1, 0, -1 };
    private static int[] dj = { 1, 0, -1, 0 };

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
//        Scanner sc = new Scanner(new FileInputStream("src\\baekjoon\\input.txt"));

        N = sc.nextInt();
        M = sc.nextInt();
        board = new char[N][M];
        Point red_marble = null;
        Point blue_marble = null;

        for (int i = 0; i < N; i++) {
            board[i] = sc.next().toCharArray();
            for (int j = 0; j < M; j++) {
                if (board[i][j] == 'R') {
                    red_marble = new Point(i, j, 1);
                }
                if (board[i][j] == 'B') {
                    blue_marble = new Point(i, j, 1);
                }
            }
        }

        // 보드를 기울인다
        moveBoard(red_marble, blue_marble, 0, 0);
        
        // 10번 넘게 움직이면 -1
        if(answer > 10) {
            answer = -1;
        }
        System.out.print(answer);
    }

    private static void moveBoard(Point red_marble, Point blue_marble, int cnt, int dir) {
        // 10번 넘게 움직이면 안 됨
        if (cnt > 10) {
            return;
        }
        
        // 빨간 구슬은 빠지고, 파란 구슬은 빠지지 않을 때
        if(red_marble.move == -1 && blue_marble.move > -1) {
            answer = Integer.min(answer, cnt);
            return;
        }
        
        for (int k = 0; k < 4; k++) {
            if(cnt > 0) {
                if(Math.abs(k - dir) == 2) {
                    continue;
                }
            }
            
            Point R_temp = new Point(red_marble.i, red_marble.j, red_marble.move);
            Point B_temp = new Point(blue_marble.i, blue_marble.j, blue_marble.move);
            
            // k방향으로 구슬을 굴린다
            boolean isRoll = rollMarble(red_marble, blue_marble, k);
            if (isRoll) { // 굴릴 수 있다면
                moveBoard(red_marble, blue_marble, cnt + 1, k);
            }
            
            red_marble = R_temp;
            blue_marble = B_temp;
        }

    }

    private static boolean rollMarble(Point red_marble, Point blue_marble, int k) {

        int ri = red_marble.i;
        int rj = red_marble.j;
        int bi = blue_marble.i;
        int bj = blue_marble.j;
        int mv = 0;
        
        while(true) {
            if(red_marble.move == 1) {
                ri += di[k];
                rj += dj[k];
            }
            if(blue_marble.move == 1) {
                bi += di[k];
                bj += dj[k];
            }
            
            if(board[ri][rj] == '#') {
                // 벽이면 멈춤
                red_marble.move = 0;
            }
            if(board[bi][bj] == '#') {
                // 벽이면 멈춤
                blue_marble.move = 0;
            }
            
            if(blue_marble.move == 0 && ri == blue_marble.i && rj == blue_marble.j) {
                // 공이 겹침
                red_marble.move = 0;
            }
            if(red_marble.move == 0 && bi == red_marble.i && bj == red_marble.j) {
                // 공이 겹침
                blue_marble.move = 0;
            }
            
            if(board[ri][rj] == 'O') {
                // 구멍이면 빠짐
                red_marble.move = -1;
                mv++;
            }
            if(board[bi][bj] == 'O') {
                // 구멍이면 빠짐
                blue_marble.move = -1;
                break;
            }
            
            // 구슬이 둘 다 멈추면 그만
            if(red_marble.move < 1 && blue_marble.move < 1) {
                break;
            }
            
            if(red_marble.move == 1) {
                red_marble.i = ri;
                red_marble.j = rj;
                mv++;
            }
            
            if(blue_marble.move == 1) {
                blue_marble.i = bi;
                blue_marble.j = bj;
                mv++;
            }
        }
        
        // 파란구슬이 빠지면 실패
        if(blue_marble.move == -1) {
            red_marble.move = 1;
            blue_marble.move = 1;
            return false;
        }
        
        // 움직이지 못했다면
        if(mv == 0) {
            red_marble.move = 1;
            blue_marble.move = 1;
            return false;
        }
        
        // 빨간구슬만 빠졌다면
        if(red_marble.move == -1 && blue_marble.move > -1) {
            red_marble.i = ri;
            red_marble.j = rj;
            return true;
        }
        
        red_marble.move = 1;
        blue_marble.move = 1;
        return true;
    }

    private static class Point {
        int i;
        int j;
        int move; // 1움직이는 중 0멈춤 -1구멍에빠짐  

        public Point(int i, int j, int move) {
            this.i = i;
            this.j = j;
            this.move = move;
        }
    }
}