[BOJ] 15653 - 구슬 탈출 4

www.acmicpc.net/problem/15653

15653번: 구슬 탈출 4

많이 어렵다... 훕냐.. 손으로 해보는게 더 쉬운듯 했다.

문제는 그냥... 그냥 반복해서 풀면 된다.. BFS 문제..

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class boj_15653 {
    static int N, M;
    static boolean visit[][][][];
    static char[][] board;
    static int MX[] = { -1,  0, 0, 1};
    static int MY[] = {  0, -1, 1, 0};
    static class PSet {
        Pos R, B;
        int num;
        PSet(Pos R, Pos B){
            this.R = R;
            this.B = B;
        }
        PSet(Pos R, Pos B, int num){
            this.R = R;
            this.B = B;
            this.num = num;
        }
    }
    static class Pos {
        int x, y;
        Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
        boolean isSame(Pos C) {
            return (this.x == C.x && this.y == C.y);
        }

        @Override
        public String toString() {
            return "{" + x +"," + y +'}';
        }
    }
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/boj_15653.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        board = new char[N+1][M+1];
        visit = new boolean[11][11][11][11];
        Pos R = null;
        Pos B = null;
        String tmp;
        int j;
        for (int i = 0; i < N ; i++) {
            tmp = br.readLine();
            board[i] = tmp.toCharArray();
            if( tmp.indexOf('R') > -1) {
                j = tmp.indexOf('R');
                R = new Pos(i,j);
                board[i][j] = '.';
            }
            if( tmp.indexOf('B') > -1) {
                j = tmp.indexOf('B');
                B = new Pos(i, j);
                board[i][j] = '.';
            }
        }

        System.out.println(solve(R, B));
    }
    static int solve(Pos R, Pos B) {
        Queue<PSet> queue = new LinkedList<>();

        PSet ps = new PSet(R, B, 0);
        queue.add(ps);

        Pos RT, BT;
        int num;
        while (!queue.isEmpty()){
            ps = queue.poll();
            RT = ps.R;
            BT = ps.B;
            num = ps.num + 1;

            if(visit[RT.x][RT.y][BT.x][BT.y]) continue;
            visit[RT.x][RT.y][BT.x][BT.y] = true;

            for (int i = 0; i < 4; i++) {
                PSet moved = move(RT, BT, i);

                if(!visit[moved.R.x][moved.R.y][moved.B.x][moved.B.y]  //움직인 R과 B가 방문한 적이 없고,
                && !(RT.isSame(moved.R) && BT.isSame(moved.B))) { //원래 R과 B와 같은 위치가 아니라면 확인해보기
                    if(board[moved.B.x][moved.B.y] == 'O') continue;  //움직인 B가 구멍에 빠지면 continue
                    else if(board[moved.R.x][moved.R.y] == 'O')  //움직인 R가 구멍에 빠지면 Num return
                        return num;
                    else {  //어디 빠진게 없으면 다음 경로에 넣어줌
                        queue.add(new PSet(moved.R, moved.B, num));
                    }
                }
            }
        }
        return -1;
    }

    static PSet move (Pos IR, Pos IB, int d) {
        Pos R = new Pos(IR.x, IR.y);
        Pos B = new Pos(IB.x, IB.y);
        PSet pset;

        // R, B 모두 움직일 수 있을때 까지 이동
        while (board[R.x][R.y] != 'O' && board[B.x][B.y] != 'O'
        && board[R.x + MX[d]][R.y + MY[d]] !='#' && board[B.x + MX[d]][B.y + MY[d]] !='#') {
            R.x += MX[d];
            R.y += MY[d];
            B.x += MX[d];
            B.y += MY[d];
        }

        // R이 더 갈 수 있을때 까지 가기
        while (board[R.x][R.y] != 'O'
        && board[R.x + MX[d]][R.y + MY[d]] !='#' && !((R.x + MX[d] == B.x) && (R.y + MY[d] == B.y))){
            R.x += MX[d];
            R.y += MY[d];
        }

        // B가 더 갈수 있을때 까지 가기
        while (board[B.x + MX[d]][B.y + MY[d]] == 'O' || board[B.x][B.y] !='O'
        && board[B.x + MX[d]][B.y + MY[d]] !='#' && !((R.x == B.x + MX[d]) && (R.y == B.y + MY[d]))) {
            B.x += MX[d];
            B.y += MY[d];
        }

        pset = new PSet(R, B);
        return pset;
    }
}

 

코드가 복잡하다,