백준 - 13460 구슬 탈출 2(Java)

구현 문제입니다.

 

구슬이 상, 하, 좌, 우로 움직였을 때 모든 경우를 bfs로 완전 탐색으로 해결했습니다.

 

[구현 코드]

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

public class Main {
    private static final String SEPARATOR = " ";

    private static int n, m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz = new StringTokenizer(br.readLine(), SEPARATOR);

        n = Integer.parseInt(stz.nextToken());
        m = Integer.parseInt(stz.nextToken());

        char[][] map = new char[n][m];

        for (int i = 0; i < n; i++) {
            char[] input = br.readLine().toCharArray();
            for (int j = 0; j < m; j++) {
                map[i][j] = input[j];
            }
        }

        int answer = bfs(map);

        if (answer > 10) answer = -1;

        bw.write(String.valueOf(answer));

        bw.flush();
        bw.close();
        br.close();
    }

    private static int bfs(char[][] initMap) {
        Queue<Board> qu = new LinkedList<>();
        qu.add(new Board(0, initMap, -1, BallState.ALL_EXIST));

        while (!qu.isEmpty()) {
            Board cn = qu.poll();

            if (cn.depth > 10) return -1;

            if (cn.ballState == BallState.ONLY_BLUE_EXIST) {
                return cn.depth;
            }

            for (int i = 0; i < 4; i++) {
                char[][] copied = copyMap(cn.map);
                BallState ballState;

                if(cn.before == i) continue;

                if (i == 0) {
                    ballState = left(copied);
                } else if (i == 1) {
                    ballState = right(copied);
                } else if (i == 2) {
                    ballState = up(copied);
                } else {
                    ballState = down(copied);
                }

                if (ballState == BallState.NOT_ALL_EXIST || ballState == BallState.ONLY_RED_EXIST) {
                    continue;
                }

                qu.add(new Board(cn.depth + 1, copied, i, ballState));

            }
        }

        return -1;
    }

    private static char[][] copyMap(char[][] map) {
        char[][] copied = new char[n][m];
        for (int i = 0; i < n; i++) {
            copied[i] = Arrays.copyOf(map[i], m);
        }
        return copied;
    }

    private static BallState up(char[][] map) {
        boolean isRedExist = true;
        boolean isBlueExist = true;

        for (int j = 1; j < m - 1; j++) {
            int[] isGate = null;
            Loop2:for (int i = 1; i < n - 1; i++) {
                if (map[i][j] == '.' || map[i][j] == 'O') {

                    if (map[i][j] == 'O') isGate = new int[]{i, j};

                    int t = i + 1;

                    while (t < n - 1) {
                        if (map[t][j] == '#') {
                            isGate = null;
                            break;
                        } else if (map[t][j] == 'R' || map[t][j] == 'B') { // 파랑 또는 빨강을 만나면
                            if (isGate == null) {
                                map[i][j] = map[t][j];
                            } else {
                                // 중력 이동 중간에 구멍이 있다면
                                if (map[t][j] == 'R') {
                                    isRedExist = false;
                                } else {
                                    isBlueExist = false;
                                }
                            }
                            map[t][j] = '.';
                            continue Loop2;
                        } else if (map[t][j] == 'O') {
                            isGate = new int[]{t, j};
                        }
                        t++;
                    }
                }
            }
            if (!isRedExist || !isBlueExist) {
                return BallState.getState(isRedExist, isBlueExist);
            }
        }
        return BallState.ALL_EXIST;
    }

    private static BallState down(char[][] map) {
        boolean isRedExist = true;
        boolean isBlueExist = true;

        for (int j = 1; j < m - 1; j++) {
            int[] isGate = null;
            Loop2:for (int i = n - 2; i >= 1; i--) {
                if (map[i][j] == '.' || map[i][j] == 'O') {

                    if (map[i][j] == 'O') isGate = new int[]{i, j};

                    int t = i - 1;

                    while (t >= 1) {
                        if (map[t][j] == '#') {
                            isGate = null;
                            break;
                        } else if (map[t][j] == 'R' || map[t][j] == 'B') { // 파랑 또는 빨강을 만나면
                            if (isGate == null) {
                                map[i][j] = map[t][j];
                            } else {
                                // 중력 이동 중간에 구멍이 있다면
                                if (map[t][j] == 'R') {
                                    isRedExist = false;
                                } else {
                                    isBlueExist = false;
                                }
                            }
                            map[t][j] = '.';
                            continue Loop2;
                        } else if (map[t][j] == 'O') {
                            isGate = new int[]{t, j};
                        }
                        t--;
                    }
                }
            }
            if (!isRedExist || !isBlueExist) {
                return BallState.getState(isRedExist, isBlueExist);
            }
        }
        return BallState.ALL_EXIST;
    }

    private static BallState left(char[][] map) {
        boolean isRedExist = true;
        boolean isBlueExist = true;

        for (int i = 1; i < n - 1; i++) {
            int[] isGate = null;
            Loop2:for (int j = 1; j < m - 1; j++) {
                if (map[i][j] == '.' || map[i][j] == 'O') {

                    if (map[i][j] == 'O') isGate = new int[]{i, j};

                    int t = j + 1;

                    while (t < m - 1) {
                        if (map[i][t] == '#') {
                            isGate = null;
                            break;
                        } else if (map[i][t] == 'R' || map[i][t] == 'B') { // 파랑 또는 빨강을 만나면
                            if (isGate == null) {
                                map[i][j] = map[i][t];
                            } else {
                                // 중력 이동 중간에 구멍이 있다면
                                if (map[i][t] == 'R') {
                                    isRedExist = false;
                                } else {
                                    isBlueExist = false;
                                }
                            }
                            map[i][t] = '.';
                            continue Loop2;
                        } else if (map[i][t] == 'O') {
                            isGate = new int[]{i, t};
                        }
                        t++;
                    }
                }
            }
            if (!isRedExist || !isBlueExist) {
                return BallState.getState(isRedExist, isBlueExist);
            }
        }
        return BallState.ALL_EXIST;
    }

    private static BallState right(char[][] map) {
        boolean isRedExist = true;
        boolean isBlueExist = true;

        for (int i = 1; i < n; i++) {
            int[] isGate = null;
            Loop2:for (int j = m - 2; j >= 1; j--) {
                if (map[i][j] == '.' || map[i][j] == 'O') {

                    if (map[i][j] == 'O') isGate = new int[]{i, j};

                    int t = j - 1;

                    while (t >= 1) {
                        if (map[i][t] == '#') {
                            isGate = null;
                            break;
                        } else if (map[i][t] == 'R' || map[i][t] == 'B') { // 파랑 또는 빨강을 만나면
                            if (isGate == null) {
                                map[i][j] = map[i][t];
                            } else {
                                // 중력 이동 중간에 구멍이 있다면
                                if (map[i][t] == 'R') {
                                    isRedExist = false;
                                } else {
                                    isBlueExist = false;
                                }
                            }
                            map[i][t] = '.';
                            continue Loop2;
                        } else if (map[i][t] == 'O') {
                            isGate = new int[]{i, t};
                        }
                        t--;
                    }
                }
            }
            if (!isRedExist || !isBlueExist) {
                return BallState.getState(isRedExist, isBlueExist);
            }
        }

        return BallState.ALL_EXIST;
    }


    private enum BallState {
        NOT_ALL_EXIST, ALL_EXIST, ONLY_RED_EXIST, ONLY_BLUE_EXIST;

        private static BallState getState(boolean red, boolean blue) {
            if (red && blue) {
                return ALL_EXIST;
            } else if (red && !blue) {
                return ONLY_RED_EXIST;
            } else if (!red && blue) {
                return ONLY_BLUE_EXIST;
            } else {
                return NOT_ALL_EXIST;
            }
        }
    }

    private static class Board {
        int depth;
        char[][] map;
        int before;
        BallState ballState;


        public Board(int depth, char[][] map, int before, BallState ballState) {
            this.depth = depth;
            this.map = map;
            this.before = before;
            this.ballState = ballState;
        }
    }
}