[JAVA] 백준 15653 구슬탈출4

15653 구슬탈출4

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

풀이법

빨간 구슬과 파란구슬을 상하좌우로 움직였을 때 최소 몇번만에 빨간 구슬을 구멍에서 빼내는지 구하는 문제로 bfs로 풀면 됨.

고민한 조건

• 빨간 공과 파란 공은 동시에 구멍에 들어가면 안됨. => 빨간 공이 구멍에 들어간 경우와 파란 공이 구멍에 들어간 경우를 표시해서 빨간공만 들어갔을 때 최솟값 출력
• 파란 공이 구멍에 들어가면 안됨. => 다음에 갈 위치를 큐에 넣지 않음
• 한쪽으로 기울었는데 빨간 공, 파란 공이 둘 다 같은 위치에 섰을 때 => 빨간 공과 파란 공 각각 움직인 횟수를 세서 더 큰 쪽을 다시 위치 1만큼 되돌리기

import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
    
    static int n,m;
    static String[][] map;
    static int min = Integer.MAX_VALUE;
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,1,0,-1};

    static class Node {
        int rx;
        int ry;
        int bx;
        int by;
        int cnt;

        public Node(int rx, int ry , int bx, int by, int cnt) {
            this.rx = rx;
            this.ry = ry;
            this.bx = bx;
            this.by = by;
            this.cnt = cnt;
        }

    }
    public static void main (String[] args) throws java.lang.Exception
    {
        System.setIn(new FileInputStream("input.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());
        map  = new String[n][m];
        int rx = 0,ry = 0,bx = 0,by = 0;
        for (int i = 0; i< n; i++) {
            String[] str = br.readLine().split("");
            for (int j = 0; j< m;j++) {
                map[i][j] = str[j];
                if (map[i][j].equals("R")) {
                    rx = i;
                    ry = j;
                } else if (map[i][j].equals("B")){
                    bx = i;
                    by = j;
                }
            }
        }

        Queue<Node> q = new LinkedList<>();
        boolean[][][][] ch = new boolean[n][m][n][m];
        
        q.add(new Node(rx, ry, bx, by, 0));
        ch[rx][ry][bx][by] = true;

        while(!q.isEmpty()) {
            Node no = q.poll();
        
            for (int i = 0; i< 4; i++) {
                int nrx = no.rx;
                int nry = no.ry;
                int nbx = no.bx;
                int nby = no.by;
                boolean rflag = false;
                boolean bflag = false;
                int rcnt = 0;
                int bcnt = 0;
                while(check(nrx + dx[i], nry + dy[i]) ) {
                    nrx += dx[i];
                    nry += dy[i];
                    rcnt++;
                    
                    if (map[nrx][nry].equals("O")) {
                        rflag = true;
                        break;
                    }
                }

                while(check(nbx + dx[i], nby + dy[i])) {
                    nbx += dx[i];
                    nby += dy[i];
                    bcnt++;
                    
                    if (map[nbx][nby].equals("O")) {
                        bflag = true;
                        break;
                    }
                }

                if (bflag) {
                    continue;
                } else if (rflag) {
                    System.out.println(no.cnt + 1);
                    return;
                } else {
                    if (nbx == nrx && nby == nry) {
                        if (rcnt > bcnt) {
                            nrx -= dx[i];
                            nry -= dy[i];
                        } else{
                            nbx -= dx[i];
                            nby -= dy[i];
                        }
                        
                    }
                }

                if (!ch[nrx][nry][nbx][nby]) {
                        ch[nrx][nry][nbx][nby] = true;
                        q.add(new Node(nrx, nry, nbx, nby, no.cnt + 1));
                }
                
                

            }
        }

        
        System.out.println("-1");
        
    }

        static boolean check(int x, int y) {
            if (x <= 0 || y <= 0 || x >= n-1 || y >= m-1) {return false;}

            if (map[x][y].equals("#")) {
                return false;
            }
            return true;
        }

}