백준 알고리즘[재귀] 13460 - 째로탈출2(다시 풀어보기)

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

소요시간 : 4시간;;;;;;;;;;;;;ㅠㅠ

   import java.util.Scanner;
    
    public class Main {
        public static char[][] maps;
        public static int n,m, min, count;
        public static int[] moveX, moveY;
        public static final int left=0,right=1,up=2,down=3;
        public static int prev;
        
        public static void main(String[] args) throws FileNotFoundException {
            //FileInputStream fi = new FileInputStream("C:\\Users\\SeonMi\\Desktop\\JavaTools\\Tools\\workspace\\Solution\\src\\data.txt");
            Scanner sc = new Scanner(System.in);
            //Scanner sc = new Scanner(fi);
            
            n = sc.nextInt();
            m = sc.nextInt();            
            maps = new char[11][11];
            min = -1; // -1로 min 초기화
            moveX = new int[]{0,0,-1,1}; //L,R,U,D
            moveY = new int[]{-1,1,0,0}; //L,R,U,Dㅣ
            
            int blueX=0, blueY=0, redX=0, redY=0;
            
            for(int i=1;i<=n;i++){
                String line = sc.next();
                char[] arr = line.toCharArray();
                for(int j=1;j<=m;j++){
                    maps[i][j] = arr[j-1];
                    if(maps[i][j]=='B'){ // Blue의 현재 위치 저장
                         blueX = i;
                         blueY = j;
                    }
                    else if(maps[i][j]=='R'){ // RED의 현재위치 저장
                        redX = i;
                        redY = j;
                    }                    
                }
            }
            move(blueX, blueY, redX, redY, 1, maps, 4);
            
            System.out.println(min);
            sc.close();
        }
 
 
        public static void move(int _blueX, int _blueY, int _redX, int _redY, int _count, char[][] _maps, int prev) {
            char[][] maps;
            int blueX,blueY,redX,redY;
 
            if(_count<=10){
                if((prev!=up && prev!=down) || prev==4) //처음(prev=4) 또는 기존에 L,R 한 경우 U 또는 D를 해준다.(prev=>next 가 같으면 제자리 걸음 그리고 R=>L 이나 L=>R 동시에 들어가거나 제자리걸음)
                {
                    // ------------------UP----------------------
                    maps = copyMaps(_maps);
                    if(_blueY==_redY && _blueX<_redX){ // 같은 라인에 있을 때, blue<red 인 경우 blue 먼저 이동
                        blueX = moveBlue(maps, up, _blueX, _blueY);
                        redX = moveRed(maps, up, _redX, _redY);
                    }
                    else{ // blue가 뒤에 있을 때 
                        redX = moveRed(maps, up, _redX, _redY);
                        blueX = moveBlue(maps, up, _blueX, _blueY);
                    }
                    if(redX==0 && blueX!=0){
                        if(min==-1)
                            min = _count;
                        else{
                            if(_count<min)
                                min = _count;
                        }
                    }
                    else if(redX!=0 && blueX!=0)
                        move(blueX, _blueY, redX, _redY, _count+1, maps,up);
                    // ------------------DOWN----------------------
                    maps = copyMaps(_maps);
                    if(_blueY==_redY && _blueX<_redX){ // 같은 라인에 있을 때, blue<red 인 경우 blue 먼저 이동
                        redX = moveRed(maps, down, _redX, _redY);
                        blueX = moveBlue(maps, down, _blueX, _blueY);
                    }
                    else{ // blue가 뒤에 있을 때 
                        blueX = moveBlue(maps, down, _blueX, _blueY);
                        redX = moveRed(maps, down, _redX, _redY);
                    }
                    if(redX==0 && blueX!=0){ // red=0, blue!=0 
                        if(min==-1)
                            min = _count;
                        else{
                            if(_count<min)
                                min = _count;
                        }
                    }
                    else if(redX!=0 && blueX!=0) // recursion
                        move(blueX, _blueY, redX, _redY, _count+1, maps,down);
 
                }
                
                if((prev!=left && prev!=right) || prev==4){
                    // ------------------LEFT----------------------
                    maps = copyMaps(_maps);
                    if(_blueX==_redX && _blueY<_redY){ // 같은 라인에 있을 때, blue<red 인 경우 blue 먼저 이동
                        blueY = moveBlue(maps, left, _blueX, _blueY);
                        redY = moveRed(maps, left, _redX, _redY);
                    }
                    else{ // blue가 뒤에 있을 때 
                        redY = moveRed(maps, left, _redX, _redY);
                        blueY = moveBlue(maps, left, _blueX, _blueY);
                    }
                    if(redY==0 && blueY!=0){
                        if(min==-1)
                            min = _count;
                        else{
                            if(_count<min){
                                min = _count;
                            }
                        }
                    }
                    else if(redY!=0 && blueY!=0)
                        move(_blueX, blueY, _redX, redY, _count+1, maps,left);
                    
                    // ------------------RIGHT----------------------
                    maps = copyMaps(_maps);
                    if(_blueX==_redX && _blueY<_redY){ // 같은 라인에 있을 때, blue<red 인 경우 RED 먼저 이동
                        redY = moveRed(maps, right, _redX, _redY);
                        blueY = moveBlue(maps, right, _blueX, _blueY);
                    }
                    else{  
                        blueY = moveBlue(maps, right, _blueX, _blueY);
                        redY = moveRed(maps, right, _redX, _redY);
                    }
                    if(redY==0 && blueY!=0){
                        if(min==-1)
                            min = _count;
                        else{
                            if(_count<min)
                                min = _count;
                        }
                    }
                    else if(redY!=0 && blueY!=0)
                        move(_blueX, blueY, _redX, redY, _count+1, maps,right);
 
                }
                                
 
            }
 
        }
        
        public static char[][] copyMaps(char[][] _maps){
            char[][] maps = new char[n+1][m+1];
            for(int i=1;i<n+1;i++){
                for(int j=1;j<m+1;j++){
                    maps[i][j] = _maps[i][j];
                }
            }
            return maps;
        }
        
        public static int moveBlue(char[][] _maps, int dir, int _blueX, int _blueY){
            char maps[][] = _maps;
            int blueX = _blueX;
            int blueY = _blueY;
            
            if(dir==left || dir==right){ // 좌 우 로 움직일 경우
                while(maps[blueX][blueY+moveY[dir]]!='#' && maps[blueX][blueY+moveY[dir]]!='R'){
                    if(maps[blueX][blueY+moveY[dir]]=='O'){
                        blueY = 0;
                        break;
                    }
                    else{ 
                        if(dir==left)
                            blueY--;
                        else if(dir==right)
                            blueY++;
                    }
                }
                if(blueY !=0 && blueY != _blueY){
                    maps[_blueX][_blueY] = '.';
                    maps[_blueX][blueY] = 'B';
                }
                if(blueY==0)
                    maps[_blueX][_blueY] = '.';
                
                return blueY;
            }
            
            else{ // 상 하 로 움직일 경우
                while(maps[blueX+moveX[dir]][blueY]!='#'&& maps[blueX+moveX[dir]][blueY]!='R'){
                    if(maps[blueX+moveX[dir]][blueY]=='O'){
                        blueX = 0; // O를 만남!!!!
                        break;
                    }
                    else{ 
 
                        if(dir==up)
                            blueX--;
                        else if(dir==down)
                            blueX++;
                    }
                }
                if(blueX !=0 && blueX != _blueX){
                    maps[_blueX][_blueY] = '.';
                    maps[blueX][_blueY] = 'B';
                }
                if(blueX==0)
                    maps[_blueX][_blueY] = '.';
                
                return blueX;
            }
        }
        
        public static int moveRed(char[][] _maps, int dir, int _redX, int _redY){
            int redX = _redX;
            int redY = _redY;
            char[][] maps = _maps;
            
            if(dir==left || dir==right){ // 좌, 우로 움직임
                while(maps[redX][redY+moveY[dir]]!='#'&& maps[redX][redY+moveY[dir]]!='B'){
                    if(maps[redX][redY+moveY[dir]]=='O'){
                        redY = 0; // O를 만남!!!!
                        break;
                    }
                    else{
                        if(dir==left){
                            redY--;
                        }
                        else if(dir==right)
                            redY++;
                    }
                }
                if(redY !=0 && redY != _redY){
                    maps[_redX][_redY] = '.';
                    maps[_redX][redY] = 'R';
                }
                if(redY==0)
                    maps[_redX][_redY]='.';
                
                return redY;
            }
            else{ // 상 하로 움직임
                while(maps[redX+moveX[dir]][redY]!='#'&&maps[redX+moveX[dir]][redY]!='B'){
                    if(maps[redX+moveX[dir]][redY]=='O'){
                        redX = 0; // O를 만남!!!!
                        break;
                    }
                    else{
                        if(dir==up)
                            redX--;
                        else if(dir==down)
                            redX++;
                    }
                }
                if(redX !=0 && redX != _redX){
                    maps[_redX][_redY] = '.';
                    maps[redX][_redY] = 'R';
                }
                if(redX==0)
                    maps[_redX][redY]='.';
                
                
                return redX;
            }
        }
        
    }

풀이 방식 : 

처음을 제외하고

 U ,D,R,L -> if(prev=='U'||prev=='D') then R or L else if(prev=='R' || prev=='L') then U or D 

식으로 UorD -> R or L -> U or D .. U,D와 L,R을 세트로 반복했다.

각 L,R,U,D 에서는 해당 방향의 앞 칸에 벽이 없고, 색이 다른 공이 없으면 움직이도록 했다.(=해당 방향의 앞 칸이 . 이면 움직이도록 함)

예외 :

L->L, R->R 은 어차피 L, R 한번 해준 것과 같으므로, prev와 next가 같지 않도록 예외 처리했다.

또한 L->R->L 처럼 좌,우 반복은 # O . R B # 처럼 동시에 O에 들어가므로 역시 예외 처리를 했다.

(내 코드는 R, B를 하나씩 움직이므로 동시에 들어가게 될 경우, R이나 B 모두 지나간 자리를 '.' 처리해준 후 R이나 B를 움직였다..)

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
public class Solution {
    static int n,m,min;
    static char[][] maps;
    static int[] moveX, moveY, redY, blue, red;
    
    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(new FileInputStream("C:\\Users\\SeonMi\\Desktop\\JavaTools\\Tools\\workspace\\SamsungGoGo\\sample_input.txt"));
        
        n = sc.nextInt();
        m = sc.nextInt();
        red = new int[2];
        blue = new int[2];
        sc.nextLine();
        maps = new char[n][m];
        for(int i=0;i<n;i++){
            String line = sc.nextLine();
            char[] lineArr = line.toCharArray();
            for(int j=0;j<m;j++){
                maps[i][j]=lineArr[j];
                if(maps[i][j]=='R'){
                    red[0]=i;
                    red[1]=j;
                }
                if(maps[i][j]=='B'){
                    blue[0]=i;
                    blue[1]=j;
                }
            }
        }
        
        moveX = new int[]{0,1,0,-1}; // R D L U
        moveY = new int[]{1,0,-1,0};
        min = 9999999;
        
        maps[red[0]][red[1]]='.';
        maps[blue[0]][blue[1]]='.';
        
        for(int i=0;i<4;i++){
            int count=0;
            move(count, i, red[0], red[1], blue[0], blue[1]);
        }
        if(min==9999999)
            min=-1;
        System.out.println(min);
        
    }
 
    static void move(int curCount, int dir, int redX, int redY, int blueX, int blueY) {
        if(curCount>=10){            
            return;
        }
        
        if(min!=-1 && curCount+1>min){            
            return;
        }
        
 
        int firstCheck = whoseFisrt(dir, redX, redY, blueX, blueY);
        boolean redEnd = false;
        boolean blueEnd = false;
        boolean isRedMove = false;
        boolean isBlueMove = false;
        
        if(firstCheck==0) // 빨간 것 먼저 움직이기
        {
            while(true){ // 빨간 공 먼저 움직이기
                if(maps[redX+moveX[dir]][redY+moveY[dir]]=='O'){
                    redEnd = true;
                    break;
                }
                else if(maps[redX+moveX[dir]][redY+moveY[dir]]=='#' 
                        || (redX+moveX[dir]==blueX && redY+moveY[dir]==blueY)){
                    break;
                }
                else{
                    redX += moveX[dir];
                    redY += moveY[dir];
                    isRedMove = true;
                }
            }        
            
            // 파란 공 움직이기
            while(true){ 
                if(maps[blueX+moveX[dir]][blueY+moveY[dir]]=='O'){
                    blueEnd = true;
                    break;
                }
                else if(maps[blueX+moveX[dir]][blueY+moveY[dir]]=='#' 
                        || (blueX+moveX[dir]==redX && blueY+moveY[dir]==redY) && !redEnd){
                    break;
                }
                else{
                    blueX += moveX[dir];
                    blueY += moveY[dir];
                    isBlueMove = true;
                }
            }
            
        }
        
        else // 파란 공 먼저 움직
        {
            
            // 파란 공 움직이기
            while(true){ 
                if(maps[blueX+moveX[dir]][blueY+moveY[dir]]=='O'){
                    blueEnd = true;
                    break;
                }
                else if(maps[blueX+moveX[dir]][blueY+moveY[dir]]=='#' 
                        || (blueX+moveX[dir]==redX && blueY+moveY[dir]==redY)){
                    
                    break;
                }
                else{
                    blueX+= moveX[dir];
                    blueY += moveY[dir];
                    isBlueMove = true;
                }
            }
            
            while(true){ // 빨간 공 먼저 움직이기
                if(maps[redX+moveX[dir]][redY+moveY[dir]]=='O'){
                    redEnd = true;
                    break;
                }
                else if(maps[redX+moveX[dir]][redY+moveY[dir]]=='#'
                        || (redX+moveX[dir]==blueX && redY+moveY[dir]==blueY  && !blueEnd)){                    
                    break;
                }
                else{
                    redX += moveX[dir];
                    redY += moveY[dir];
                    isRedMove = true;
                }
            }
 
        }
 
        
        if(blueEnd){
            if(min==9999999){
                min = -1;
            }
            return;
        }
        else if(redEnd){
            if(min==-1 || min==9999999)
                min = curCount+1;
            else{
                min = Math.min(curCount+1, min);    
            }
            return;
        }
 
        else if((!isRedMove && !isBlueMove)){
            return;
        }
        else{
            if(dir==0 || dir==2){
                move(curCount+1, 1, redX, redY, blueX, blueY);
                move(curCount+1, 3, redX, redY, blueX, blueY);
            }
            else{
                move(curCount+1, 0, redX, redY, blueX, blueY);
                move(curCount+1, 2, redX, redY, blueX, blueY);
            }
        
        }
 
        return;
        
    }
 
    static int whoseFisrt(int dir, int redX, int redY, int blueX, int blueY) {
        switch(dir){
        case 0:
            if(redX==blueX&& redY>blueY)
                return 0;
            else
                return 1;
        case 1:
            if(redX<blueX && redY==blueY)
                return 1;
            else
                return 0;
        case 2:
            if(redX==blueX && redY>blueY)
                return 1;
            else
                return 0;
        case 3:
            if(redX<blueX && redY==blueY)
                return 0;
            else
                return 1;
        default:
            return 0;
        }
    }
 
}