[백준] 13460 구슬 탈출 2

 

java를 이용해서 문제를 풀어봤다

먼저 모든 방법의 수는 4^10이므로 2^20이랑 같고

완탐으로 충분히 가능하기 때문에 모든 경우의 수를 돌려봤다

 

4방향을 한번씩 가면서 dfs를 이용하면 된다

방향을 정한 다음에는 R > B > R 순서대로 공을 굴려봤다

R을 두번 굴리는 이유는 R이 B 뒤에있어서 B에 막힌다면 

B가 움직이고 똑같은 거리만큼 더 가야하기 때문에 한번 더 보내보는 경우다

 

근데 답을 체크해주는 부분을 함수에서 잘못 설정해서 모든 경우를 못봤다

그래서 틀렸다..!!! 

복잡할수록 천천히 신중하게 코드를 짜야겠다..!

 

소스코드

import java.util.*;
import java.io.*;
 
 
public class Main {
    public static int Rx,Ry,Bx,By,Ox,Oy,n,m,answer=11;
    public static int[] dx = {0,0,-1,1};
    public static int[] dy = {1,-1,0,0};
    public static char[][] map;
    
    public static boolean inner(int x,int y) {
        return (0<=x && x<n && 0<=y && y<m);
    }
    
    public static void move(int p) {
        map[Rx][Ry]='.'; 
        int nx = Rx+dx[p]; int ny = Ry+dy[p];
        while(inner(nx,ny) && (map[nx][ny] =='.' || map[nx][ny]=='O')) {
            Rx=nx; Ry=ny;
            nx+=dx[p]; ny+=dy[p];
            if(map[Rx][Ry]=='O') break;
        }        
        map[Rx][Ry] = (map[Rx][Ry] == 'O') ? 'O' : 'R';
        
        if(map[Bx][By]=='O') return;
        map[Bx][By]='.';
        nx = Bx+dx[p]; ny = By+dy[p];
        while(inner(nx,ny) && (map[nx][ny] =='.' || map[nx][ny]=='O')) {
            Bx=nx; By=ny;
            nx+=dx[p]; ny+=dy[p];
            if(map[Bx][By]=='O') break;
        }        
        map[Bx][By] = (map[Bx][By]=='O') ? 'O' : 'B';
        
        if(map[Rx][Ry]=='O') return;
        
        map[Rx][Ry]='.';
        nx = Rx+dx[p]; ny = Ry+dy[p];
        while(inner(nx,ny) && (map[nx][ny] =='.' || map[nx][ny]=='O')) {
            Rx=nx; Ry=ny;
            nx+=dx[p]; ny+=dy[p];
            if(map[Rx][Ry]=='O') break;
        }        
        map[Rx][Ry] = (map[Rx][Ry] == 'O') ? 'O' : 'R';
    }
    public static void solve(int cnt) {
        if(cnt==11) return;
        if(map[Bx][By]=='O') return;
        if(map[Rx][Ry]=='O') {
            answer = Math.min(answer, cnt); return;
        }
        
        int nRx = Rx,nRy = Ry;
        int nBx = Bx,nBy = By;
        
        for(int i=0;i<4;i++) {
            move(i);
            solve(cnt+1);
            map[Rx][Ry] = (map[Rx][Ry]=='O') ? 'O' : '.';
            map[Bx][By] = (map[Bx][By]=='O') ? 'O' : '.';
            
            Rx = nRx; Ry = nRy;
            Bx = nBx; By = nBy;
            map[Rx][Ry]='R';
            map[Bx][By]='B';
        }
    }
    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        map = new char[n+1][m+1];
        
        for(int i=0;i<n;i++) {
            String s = sc.next();
            char[] ca = s.toCharArray();
            for(int j=0;j<m;j++) {
                map[i][j] = ca[j];
                if(map[i][j] == 'R') {
                    Rx=i; Ry=j;
                }
                else if(map[i][j]=='B') {
                    Bx=i; By=j;
                }
                else if(map[i][j]=='O') {
                    Ox=i; Oy=j;
                }
            }
        }
    
        solve(0);
        answer = (answer==11) ? -1 : answer;
        System.out.println(answer);
    }
}