백준 - 13460번

풀이

 

import java.io.*;

import java.util.LinkedList;

import java.util.Queue;

 

public class Main {

      static int[][] rboArea = {{0, 0}, {0, 0}, {0, 0}}; // R, B, O 위치 값

      static int x = 0, y = 0; // 입력받은 열, 행

      static String[][] arr = null; // 입력받은 배열

      static boolean[][][][] visited = null; // 방문 배열

      static int[][] drFlow = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 열/행 증/감 배열

 

      public static void main(String[] args) throws Exception {

            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

 

            String[] inputList = br.readLine().split(" ");

            x = Integer.parseInt(inputList[0]); // 열 Setting

            y = Integer.parseInt(inputList[1]); // 행 Setting

            arr = new String[x][y];

            visited = new boolean[x][y][x][y];

 

            for(int i=0; i<x; i++) {

                  makeArr(br.readLine(), i);

            }

 

            System.out.print(findRode());

 

            br.close();

      }

 

      // 입력받은 데이터로 배열 생성 함수

      private static void makeArr(String str, int num) {

            int chkR = str.indexOf("R"); // R 위치

            int chkB = str.indexOf("B"); // B 위치

            int chkO = str.indexOf("O"); // O 위치

 

            if(chkR != -1) {

                  rboArea[0][0] = num;

                  rboArea[0][1] = chkR;

            }

 

            if(chkB != -1) {

                  rboArea[1][0] = num;

                  rboArea[1][1] = chkB;

            }

 

            if(chkO != -1) {

                  rboArea[2][0] = num;

                  rboArea[2][1] = chkO;

            }

 

            arr[num] = str.split("");

      }

 

      // 최단 경로 찾기

      private static int findRode() {

            Queue<Node> q = new LinkedList<>();

            q.add(new Node(rboArea[0][0], rboArea[0][1], rboArea[1][0], rboArea[1][1], 1));

 

            while(!q.isEmpty()) {

                  Node node = q.poll();

                  int originRX = node.rX, originRY = node.rY; // R의 위치

                  int originBX = node.bX, originBY = node.bY; // B의 위치

                  int depth = node.depth;

 

                  visited[originRX][originRY][originBX][originBY] = true;

 

                  if(depth > 10) return -1; // 10회 넘으면 실패

 

                  for(int i=0; i<4; i++) {

                        int moveX = drFlow[i][0];

                        int moveY = drFlow[i][1];

                        int rX = node.rX, rY = node.rY; // 기울였을 때 R의 위치

                        int bX = node.bX, bY = node.bY; // 기울였을 때 B의 위치

 

                        boolean rIn = false, bIn = false; // R과 B가 O 에 들어갔는지 체크

 

                        while(!arr[rX + moveX][rY + moveY].equals("#")) { // 벽이 나올 때까지 R 이동

                              if(arr[rX + moveX][rY + moveY].equals("O")) {

                                    rIn = true;

                                    break;

                              }

                              rX += moveX;

                              rY += moveY;

                        }

 

                        while(!arr[bX + moveX][bY + moveY].equals("#")) { // 벽이 나올 때까지 B 이동

                              if(arr[bX + moveX][bY + moveY].equals("O")) {

                                    bIn = true;

                                    break;

                              }

                              bX += moveX;

                              bY += moveY;

                        }

 

                        if(bIn) {

                              continue;

                        } else if(rIn) {

                              return depth;

                        }

 

                        // R과 B 위치가 같은 경우

                        if(rX == bX && rY == bY) {

                              if(i == 0) { // 위

                                    if(originRX < originBX) {

                                          bX++;

                                    } else {

                                          rX++;

                                    }

                              } else if(i == 1) { // 아래

                                    if(originRX < originBX) {

                                          rX--;

                                    } else {

                                          bX--;

                                    }

                              } else if(i == 2) { // 왼쪽

                                    if(originRY < originBY) {

                                          bY++;

                                    } else {

                                          rY++;

                                    }

                              } else if(i == 3) { // 오른쪽

                                    if(originRY < originBY) {

                                          rY--;

                                    } else {

                                          bY--;

                                    }

                              }

                        }

 

                        if(!visited[rX][rY][bX][bY]) {

                              q.add(new Node(rX, rY, bX, bY, depth+1));

                              visited[rX][rY][bX][bY] = true;

                        }

                  }

            }

 

            return -1;

      }

}

 

class Node {

      int rX, rY; // R 위치

      int bX, bY; // B 위치

      int depth; // 횟수

 

      Node(int _rX, int _rY, int _bX, int _bY, int _depth) {

            this.rX = _rX;

            this.rY = _rY;

            this.bX = _bX;

            this.bY = _bY;

            this.depth = _depth;

      }

}