[JAVA] 백준 13460: 구슬 탈출2

 

import java.util.Scanner;


 
public class baekjoon13460 {
    static int n;
    static int m;
    static char[][] info;
     
    static int[] aryH = new int[] { -1, 1, 0, 0 };
    static int[] aryW = new int[] { 0, 0, -1, 1 };
    static int res = -1;
 
    public static void main(String[] args) {                
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        info = new char[n][m];
        int h1 = 0;
        int h2 = 0;
        int w1 = 0;
        int w2 = 0;
        for (int i = 0; i < n; i++) {
            String temp = sc.next();
            for (int j = 0; j < m; j++) {
                info[i][j] = temp.charAt(j);
                if (temp.charAt(j) == 'R') {
                    h1 = i;
                    w1 = j;
                }
                if (temp.charAt(j) == 'B') {
                    h2 = i;
                    w2 = j;
                }                
            }
        }
        Position position = new Position(h1, w1, h2, w2);
        dfs(position, 1);
        System.out.println(res);
 
    }
 
    static void dfs(Position position, int count) {
        if (count > 10) {
            return;
        }
 
        for (int i = 0; i < 4; i++) {
            int redH = position.h1 + aryH[i];
            int redW = position.w1 + aryW[i];
            int blueH = position.h2 + aryH[i];
            int blueW = position.w2 + aryW[i];
             
            boolean isRedBreak = false;
            boolean isBlueBreak = false;
            int redMove = 0;
            int blueMove = 0;
            // 다음 위치가 벽이 아닌 경우는 벽을 만날 때 까지 빨간공을 굴린다.
            // 벽으로 가다가 구멍을 만나면 탈출! (isRedBreak = True)
            // 벽을 만나면 벽 만나기 전 위치로 이동!

            // 다음 위치가 벽이 아닌 경우는 벽을 만날 때 까지 파란공을 굴린다.
            // 벽으로 가다가 구멍을 만나면 탈출 실패! (isBlueBreak = True)
            // 벽을 만나면 벽 만나기 전 위치로 이동!

            // 다음 위치가 벽 인 경우는 이전 위치로 이동                        
            
            // 둘다 동일한 위치에 존재할 경우
            // 더 많이 움직인 공이 이전 칸으로 이동


            if (info[redH][redW] != '#') {                            
                while (info[redH][redW] != '#') {
                    redMove++;
                    if (info[redH][redW] == 'O') {                        
                        isRedBreak = true;
                    }
                    redH += aryH[i];
                    redW += aryW[i];                    
                }                                                
            }
 
            if (info[blueH][blueW] != '#') {               
                while (info[blueH][blueW] != '#') {
                    blueMove++;
                    if (info[blueH][blueW] == 'O') {                        
                        isBlueBreak = true;
                    }
                    blueH += aryH[i];
                    blueW += aryW[i];                    
                }                
            }

            if (info[redH][redW] == '#') {
                redH -= aryH[i];
                redW -= aryW[i];
            }

            if (info[blueH][blueW] == '#') {
                blueH -= aryH[i];
                blueW -= aryW[i];
            }

            if (redH == blueH && redW == blueW) {                
                if (redMove > blueMove) {                    
                    redH -= aryH[i];                    
                    redW -= aryW[i];                    
                } 
                if (blueMove > redMove) {
                    blueH -= aryH[i];                    
                    blueW -= aryW[i];                    
                } 
            }

            if (isBlueBreak) {                
                continue;
            }
            

            if (isRedBreak && !isBlueBreak) {
                if (res == -1) {
                    res = count;
                    return;
                } else {
                    res = Math.min(res, count);
                    return;
                }
            }                                    
            
            if (!isRedBreak && !isBlueBreak) {                
                dfs(new Position(redH, redW, blueH, blueW), count + 1);
            }
        }
    }
}
 
class Position {
    int h1;
    int w1;
    int h2;
    int w2;
 
    Position(int h1, int w1, int h2, int w2) {
        this.h1 = h1;
        this.w1 = w1;
        this.h2 = h2;
        this.w2 = w2;
    }
}