백준 13460 자바 - 구슬 탈출 2 문제

구현은 bfs를 통해서 모든 방향으로 기울여가면서 답을 구하면된다.

 

첫 위치서 부터 bfs를 통해 상하좌우로 기울여보면서 각각의 위치와 기울인 횟수를 체크

기울여서 구슬을 이동시킬때 서로에 대한 고려를 하지않고 이동시킨 뒤 

서로의 위치가 동일한 경우만 더 많이 이동한쪽을 덜이동시키도록 함

이렇게 bfs를 진행하다가 빨간 구슬만 빠져나간 경우 해당 count를 print함.

import java.io.*;
import java.util.*;

class Ball {
    int x;
    int y;
    int count;

    public Ball(int x,int y, int count) {
        this.x = x;
        this.y = y;
        this.count = count;
    }
}

// 구슬 탈출 2 문제 - 13460번
public class Main{

    static int N,M;
    static char[][] map;
    static Ball r_ball, b_ball;
    static boolean[][][][] visited;
    static int result = -1;
    //상하좌우
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static void bfs(Ball r_ball, Ball b_ball) {
        Queue<Ball> redQ = new LinkedList<>();
        Queue<Ball> blueQ = new LinkedList<>();

        redQ.offer(r_ball);
        blueQ.offer(b_ball);

        // 빨간 구슬과 파란구슬의 위치 방문 처리
        visited[r_ball.x][r_ball.y][b_ball.x][b_ball.y]= true;

        while (!redQ.isEmpty() && !blueQ.isEmpty()) {
            Ball nr_ball = redQ.poll();
            Ball nb_ball = blueQ.poll();

            if(nr_ball.count > 10) {
                result = -1;
                return;
            }

            // 파란색이 빠져나간 경우
            if(map[nb_ball.x][nb_ball.y] == 'O') {
                continue;
            }

            // 빨간 색이 빠져나가고 파란색은 빠져 나가지않은 경우
            if(map[nr_ball.x][nr_ball.y] == 'O') {
                result = nr_ball.count;
                return;
            }

            //상하좌우로 기울이기
            for(int i = 0; i < 4; i++) {

                // 기울였을때 파란 구슬이 도달하는 지점으로 이동
                int bx = nb_ball.x;
                int by = nb_ball.y;
                while(true) {
                    bx += dx[i];
                    by += dy[i];
                    // 빠져나간 경우
                    if(map[bx][by] == 'O') break;
                    // 벽을 만난 경우
                    else if(map[bx][by] == '#'){
                        bx -= dx[i];
                        by -= dy[i];
                        break;
                    }
                }

                /// 기울였을때 빨간 구슬이 도달하는 지점으로 이동
                int rx = nr_ball.x;
                int ry = nr_ball.y;
                while(true) {
                    rx += dx[i];
                    ry += dy[i];
                    // 빠져나간 경우
                    if(map[rx][ry] == 'O') break;
                        // 벽을 만난 경우
                    else if(map[rx][ry] == '#'){
                        rx -= dx[i];
                        ry -= dy[i];
                        break;
                    }
                }

                // 만약 두개의 위치가 동일하고 둘의 위치가 빠져나가는 위치가 아닌 경우 - 앞선 두개의 구슬 이동에서 서로에 대한 고려를 하지않고 이동하였기 때문에
                if(bx == rx && by == ry && map[rx][ry] != 'O') {
                    // 이동한 거리가 더 긴 쪽이 덜 이동하게 처리
                    int r_dis = Math.abs(nr_ball.x - rx) + Math.abs(nr_ball.y - ry);
                    int b_dis = Math.abs(nb_ball.x - bx) + Math.abs(nb_ball.y - by);

                    // 빨간 구슬이 더 이동한 경우
                    if(r_dis > b_dis) {
                        rx -= dx[i];
                        ry -= dy[i];
                    }
                    // 파란 구슬이 더 이동한 경우
                    else {
                        bx -= dx[i];
                        by -= dy[i];
                    }
                }

                // 기울였을때 구슬들이 도달하는 지점을 방문 처리 후 큐에 추가 - 두 구슬 중 이전과 하나라도 다르다면 다른결과가 있을수 있음
                if(!visited[rx][ry][bx][by]) {
                    // 방문처리
                    visited[rx][ry][bx][by] = true;
                    // 두 구슬을 큐에 추가
                    redQ.offer(new Ball(rx, ry, nr_ball.count + 1));
                    blueQ.offer(new Ball(bx, by, nb_ball.count + 1));
                }
            }

        }
    }

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map= new char[N][M];
        visited = new boolean[N][M][N][M];

        for(int i = 0; i < N; i++) {
            String row = br.readLine();
            for(int j = 0; j < M; j++) {
                map[i][j] = row.charAt(j);
                if(map[i][j] == 'R') {
                    r_ball = new Ball(i, j,0);
                }
                else if(map[i][j] == 'B') {
                    b_ball = new Ball(i, j,0);
                }
            }
        }
        bfs(r_ball, b_ball);
        System.out.println(result);
    }
}

 

위의 풀이의 경우 자료구조를 구슬하나에 대해서 만들었기 때문에 두개의 큐사용하게 되는데

두개의 구슬에 대한 자료 구조를 만들어서 하나의 큐만 운용해서 풀수 있음.

위에 큰 차이없이 

Ball -> TwoBall 로 변경하고 그에 맞추어 변수를 셋팅한거 뿐이다.

 

import java.io.*;
import java.util.*;

class TwoBall {
    int rx;
    int ry;
    int bx;
    int by;
    int count;

    public TwoBall(int rx,int ry, int bx, int by, int count) {
        this.rx = rx;
        this.ry = ry;
        this.bx = bx;
        this.by = by;
        this.count = count;
    }
}

// 구슬 탈출 2 문제 - 13460번
public class Main{

    static int N,M;
    static char[][] map;
    static TwoBall twoBall;
    static boolean[][][][] visited;
    static int result = -1;
    //상하좌우
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static void bfs(TwoBall twoBall) {
        Queue<TwoBall> q = new LinkedList<>();
        q.offer(twoBall);

        // 빨간 구슬과 파란구슬의 위치 방문 처리
        visited[twoBall.rx][twoBall.ry][twoBall.bx][twoBall.by]= true;

        while (!q.isEmpty()) {
            TwoBall now = q.poll();

            if(now.count > 10) {
                result = -1;
                return;
            }

            // 파란색이 빠져나간 경우
            if(map[now.bx][now.by] == 'O') {
                continue;
            }

            // 빨간 색이 빠져나가고 파란색은 빠져 나가지않은 경우
            if(map[now.rx][now.ry] == 'O') {
                result = now.count;
                return;
            }

            //상하좌우로 기울이기
            for(int i = 0; i < 4; i++) {

                // 기울였을때 파란 구슬이 도달하는 지점으로 이동
                int bx = now.bx;
                int by = now.by;
                while(true) {
                    bx += dx[i];
                    by += dy[i];
                    // 빠져나간 경우
                    if(map[bx][by] == 'O') break;
                    // 벽을 만난 경우
                    else if(map[bx][by] == '#'){
                        bx -= dx[i];
                        by -= dy[i];
                        break;
                    }
                }

                /// 기울였을때 빨간 구슬이 도달하는 지점으로 이동
                int rx = now.rx;
                int ry = now.ry;
                while(true) {
                    rx += dx[i];
                    ry += dy[i];
                    // 빠져나간 경우
                    if(map[rx][ry] == 'O') break;
                        // 벽을 만난 경우
                    else if(map[rx][ry] == '#'){
                        rx -= dx[i];
                        ry -= dy[i];
                        break;
                    }
                }

                // 만약 두개의 위치가 동일하고 둘의 위치가 빠져나가는 위치가 아닌 경우 - 앞선 두개의 구슬 이동에서 서로에 대한 고려를 하지않고 이동하였기 때문에
                if(bx == rx && by == ry && map[rx][ry] != 'O') {
                    // 이동한 거리가 더 긴 쪽이 덜 이동하게 처리
                    int r_dis = Math.abs(now.rx - rx) + Math.abs(now.ry - ry);
                    int b_dis = Math.abs(now.bx - bx) + Math.abs(now.by - by);

                    // 빨간 구슬이 더 이동한 경우
                    if(r_dis > b_dis) {
                        rx -= dx[i];
                        ry -= dy[i];
                    }
                    // 파란 구슬이 더 이동한 경우
                    else {
                        bx -= dx[i];
                        by -= dy[i];
                    }
                }

                // 기울였을때 구슬들이 도달하는 지점을 방문 처리 후 큐에 추가 - 두 구슬 중 이전과 하나라도 다르다면 다른결과가 있을수 있음
                if(!visited[rx][ry][bx][by]) {
                    // 방문처리
                    visited[rx][ry][bx][by] = true;
                    // 두 구슬을 큐에 추가
                    q.offer(new TwoBall(rx, ry, bx, by, now.count + 1));
                }
            }

        }
    }

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map= new char[N][M];
        visited = new boolean[N][M][N][M];

        int rx = 0, ry = 0, bx = 0, by = 0;

        for(int i = 0; i < N; i++) {
            String row = br.readLine();
            for(int j = 0; j < M; j++) {
                map[i][j] = row.charAt(j);
                if(map[i][j] == 'R') {
                   rx = i;
                   ry = j;
                }
                else if(map[i][j] == 'B') {
                    bx = i;
                    by = j;
                }
            }
        }
        bfs(new TwoBall(rx, ry, bx, by,0));
        System.out.println(result);
    }
}