백준 알고리즘 - 구슬탈출2

이 문제의 핵심은 어떤 구슬을 먼저 움직여 줄 지인 것 같다.
처음에 놓여진 빨간 구슬과 파란 구슬의 좌표값을 이용해서 우선순위 정해주기
#. . . RB.# 의 경우 왼쪽으로 굴리면 R부터 움직이고 B는 다음에 움직이고,
오른쪽으로 굴리면 B부터 굴리고 R을 다음에 굴린다.

구슬 이동 로직은 재귀를 이용해서 #을 만나거나 O 구멍을 만날 때 까지 계속 호출했다.

이 문제도 결국 최대 10번이다.
4의 10제곱의 경우의 수만 고려하면 된다.
1024 * 1024 는 100만이 조금 넘는다.

100만가지의 경우의 수를 검색해서 구슬이 탈출가능한 지
가능 하다면 최소 몇번만에 빠져가는지 구하면 된다.

하지만 100만가지를 다 검사하니 시간초과가 났다.
그래서 의미없는 움직임을 제외 시켜주니 통과됬다.

1. 같은 방향으로 연속해서 움직이는 경우
2. 왔던 방향으로 움직이는 경우

2가지만 제외해줘도 검사하는 경우의 수가 현저히 줄어든다.

import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;

public class Main {
    static class InObject {
        int y;
        int x;
        int originY;
        int originX;
        String type;
    }
    private static HashSet<Integer> results = new HashSet<>();
    public static void main(String[] args) {
        InObject red = new InObject();
        InObject blue = new InObject();
        Scanner scn = new Scanner(System.in);
        int n = scn.nextInt();
        int m = scn.nextInt();
        String[][] ground = new String[n][m];
        for (int i = 0; i < n; i++) {
            String[] temp = scn.next().split("");
            for (int j = 0; j < m; j++) {
                if (temp[j].equals("R")) {
                    red.y = i;
                    red.x = j;
                    red.originY = i;
                    red.originX = j;
                    red.type = "R";
                } else if (temp[j].equals("B")) {
                    blue.y = i;
                    blue.x = j;
                    blue.originY = i;
                    blue.originX = j;
                    blue.type = "B";
                }
                ground[i][j] = temp[j];
            }
        }
        scn.close();
        int[] directions = new int[10];
        for (int i = 0; i < 4; i++) {
            DFS(0, i, ground, red, blue, directions);
        }
        if (results.size() == 1) {
            System.out.println(-1);
        } else {
            int minValue = 11;
            Iterator<Integer> iterator = results.iterator();
            while (iterator.hasNext()) {
                int temp = iterator.next();
                if (temp != -1 && minValue > temp)
                    minValue = temp;
            }
            System.out.println(minValue);
        }
    }
    private static void DFS(int depth, int direction, String[][] ground, InObject red, InObject blue, int[] directions) {
        directions[depth] = direction;
        if (depth == 9) {
            for (int i = 0; i < directions.length; i++) {
                moveBeads(directions[i], ground, red, blue);
                if (checkBeads(red) && !checkBeads(blue)) {
                    resetEvery(red, blue, ground, true, i+1);
                    return;
                } else if (checkBeads(blue)) {
                    resetEvery(red, blue, ground, false, i+1);
                    return;
                }
            }
            resetEvery(red, blue, ground, false, 0);
            return;
        }
        for (int i = 0; i < 4; i++) {
            if (directions[depth] == i)
                continue;
            if (Math.abs(directions[depth] - i) == 2)
                continue;
            DFS(depth + 1, i, ground, red, blue, directions);
        }
    }
    private static void resetEvery(InObject red, InObject blue, String[][] ground, boolean tf, int cnt) {
        if (tf) {
            results.add(cnt);
        } else {
            results.add(-1);
        }
        resetBeads(red, ground);
        resetBeads(blue, ground);
    }
    private static void resetBeads(InObject bead, String[][] ground) {
        if (bead.y == 0 && bead.x == 0) {
            ground[bead.y][bead.x] = "#";
        } else {
            ground[bead.y][bead.x] = ".";
        }
        bead.y = bead.originY;
        bead.x = bead.originX;
        ground[bead.y][bead.x] = bead.type;
    }
    private static boolean checkBeads(InObject bead) {
        boolean isFall = false;
        if (bead.y == 0 && bead.x == 0)
            isFall = true;
        return isFall;
    }
    private static void moveBeads(int direction, String[][] ground, InObject red, InObject blue) {
        switch (direction) {
            case 0://up
                if (red.y - blue.y < 0) {
                    moveBeadUp(ground, red);
                    moveBeadUp(ground, blue);
                } else {
                    moveBeadUp(ground, blue);
                    moveBeadUp(ground, red);
                }
                break;
            case 1://right
                if (red.x - blue.x < 0) {
                    moveBeadRight(ground, blue);
                    moveBeadRight(ground, red);
                } else {
                    moveBeadRight(ground, red);
                    moveBeadRight(ground, blue);
                }
                break;
            case 2://down
                if (red.y - blue.y > 0) {
                    moveBeadDown(ground, red);
                    moveBeadDown(ground, blue);
                } else {
                    moveBeadDown(ground, blue);
                    moveBeadDown(ground, red);
                }
                break;
            case 3://left
                if (red.x - blue.x < 0) {
                    moveBeadLeft(ground, red);
                    moveBeadLeft(ground, blue);
                } else {
                    moveBeadLeft(ground, blue);
                    moveBeadLeft(ground, red);
                }
                break;
        }
    }
    private static void moveBeadDown(String[][] ground, InObject bead) {
        if (ground[bead.y + 1][bead.x].equals(".")) {
            ground[bead.y][bead.x] = ".";
            ground[bead.y + 1][bead.x] = bead.type;
            bead.y += 1;
            moveBeadDown(ground, bead);
        } else if (ground[bead.y + 1][bead.x].equals("#")) {
            return;
        } else if (ground[bead.y + 1][bead.x].equals("O")) {
            fallIntoHole(ground, bead);
            return;
        }
    }
    private static void moveBeadUp(String[][] ground, InObject bead) {
        if (ground[bead.y - 1][bead.x].equals(".")) {
            ground[bead.y][bead.x] = ".";
            ground[bead.y - 1][bead.x] = bead.type;
            bead.y -= 1;
            moveBeadUp(ground, bead);
        } else if (ground[bead.y - 1][bead.x].equals("#")) {
            return;
        } else if (ground[bead.y - 1][bead.x].equals("O")) {
            fallIntoHole(ground, bead);
            return;
        }
    }
    private static void moveBeadRight(String[][] ground, InObject bead) {
        if (ground[bead.y][bead.x + 1].equals(".")) {
            ground[bead.y][bead.x] = ".";
            ground[bead.y][bead.x + 1] = bead.type;
            bead.x += 1;
            moveBeadRight(ground, bead);
        } else if (ground[bead.y][bead.x + 1].equals("#")) {
            return;
        } else if (ground[bead.y][bead.x + 1].equals("O")) {
            fallIntoHole(ground, bead);
            return;
        }
    }
    private static void moveBeadLeft(String[][] ground, InObject bead) {
        if (ground[bead.y][bead.x - 1].equals(".")) {
            ground[bead.y][bead.x] = ".";
            ground[bead.y][bead.x - 1] = bead.type;
            bead.x -= 1;
            moveBeadLeft(ground, bead);
        } else if (ground[bead.y][bead.x - 1].equals("#")) {
            return;
        } else if (ground[bead.y][bead.x - 1].equals("O")) {
            fallIntoHole(ground, bead);
            return;
        }
    }
    private static void fallIntoHole(String[][] ground, InObject bead) {
        ground[bead.y][bead.x] = ".";
        bead.x = 0;
        bead.y = 0;
    }
}