백준 알고리즘 - 구슬탈출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;
    }
}

댓글

이 블로그의 인기 게시물

About JVM Warm up

About idempotent

About Kafka Basic

About ZGC

sneak peek jitpack

Spring Boot Actuator readiness, liveness probes on k8s

About Websocket minimize data size and data transfer cost on cloud

About G1 GC

대학생 코딩 과제 대행 java, python, oracle 네 번째