글 읽기 - 반례가 어떤게 있을까요? 도와주세요~

pmn0001 1년 전 0

테케는 다 맞고 제 눈에는 로직도 문제 없어보이는데 자꾸 틀리네요
어디가 문제일까요??
public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        Board[] boards = new Board[5];
        for (int i = 0; i < 5; ++i) {
            int[][] board = new int[5][5];

            for (int j = 0; j < 5; ++j) {
                st = new StringTokenizer(br.readLine(), " ");

                for (int k = 0; k < 5; ++k) {
                    board[j][k] = Integer.parseInt(st.nextToken());
                }
            }

            boards[i] = new Board(board);
        }

        Maze maze = new Maze(boards);

        System.out.println(maze.findMinDistance());
    }

    static class Maze {
        static int[] dh = {0, 0, 0, 0, -1, 1};
        static int[] dr = {-1, 0, 1, 0, 0, 0};
        static int[] dc = {0, -1, 0, 1, 0, 0};

        static int[] order = new int[5];
        static boolean[] isSelected = new boolean[5];

        Board[] boards;
        int minDistance;

        Maze(Board[] boards) {
            this.boards = boards;
            minDistance = Integer.MAX_VALUE;
        }

        int findMinDistance() {
            factorial(0); // 각 판의 순서를 결정한다.
            return this.minDistance == Integer.MAX_VALUE ? -1 : this.minDistance;
        }

        private void factorial(int idx) {
            if (idx == 5) { // 각 판의 순서가 결정되는 경우
                Board[] newBoards = new Board[5];
                for (int i = 0; i < 5; ++i) {
                    newBoards[i] = boards[order[i]];
                }

                for (int i = 0; i < 5; ++i) {
                    boards[i] = newBoards[i];
                }

                this.turn(0); // 각 판을 회전시켜본다.
                return;
            }

            for (int i = 0; i < 5; ++i) {
                if (!isSelected[i]) {
                    isSelected[i] = true;
                    order[idx] = i;
                    factorial(idx + 1);
                    isSelected[i] = false;
                }
            }
        }

        private void turn(int idx) {
            if (idx == 5) {
                this.simulate();
                return;
            }

            for (int i = 0; i < 4; ++i) { // 각 판마다 4번씩 회전시켜본다
                this.boards[idx].turn();
                turn(idx + 1);
            }
        }

        private void simulate() {
            if (!canStart() || !canEnd()) {
                return;
            }

            boolean[][][] isVisit = new boolean[5][5][5];
            Queue<Point> q = new LinkedList<>();
            isVisit[0][0][0] = true;
            q.add(new Point(0, 0, 0));

            int dist = 0;
            while (!q.isEmpty()) {
                if (dist >= minDistance) {
                    return;
                }
                int size = q.size();
                for (int i = 0; i < size; ++i) {
                    Point curr = q.poll();
                    if (curr.isEnd()) {
                        minDistance = Math.min(minDistance, dist);
                        return;
                    }

                    for (int j = 0; j < 6; ++j) {
                        int nh = curr.h + dh[j];
                        int nr = curr.r + dr[j];
                        int nc = curr.c + dc[j];

                        if (nh < 0 || nh >= 5 || nr < 0 || nr >= 5 || nc < 0 || nc >= 5
                        || boards[nh].board[nr][nc] == 0 || isVisit[nh][nr][nc]) {
                            continue;
                        }

                        isVisit[nh][nr][nc] = true;
                        q.add(new Point(nh, nr, nc));
                    }
                }
                dist++;
            }
        }

        private boolean canStart() {
            return this.boards[0].board[0][0] == 1;
        }

        private boolean canEnd() {
            return this.boards[4].board[4][4] == 1;
        }

    }

    static class Board {
        int[][] board;

        Board(int[][] board) {
            this.board = board;
        }

        void turn() {
            int[][] turnedBoard = new int[5][5];

            for (int i = 0; i < 5; ++i) {
                for (int j = 0; j < 5; ++j) {
                    turnedBoard[j][5 - i - 1] = board[i][j];
                }
            }

            for (int i = 0; i < 5; ++i) {
                for (int j = 0; j < 5; ++j) {
                    board[i][j] = turnedBoard[i][j];
                }
            }
        }
    }

    static class Point {
        int h, r, c;

        public Point(int h, int r, int c) {
            this.h = h;
            this.r = r;
            this.c = c;
        }

        public boolean isEnd() {
            return h == 4 && r == 4 && c == 4;
        }
    }
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

반례가 어떤게 있을까요? 도와주세요~

pmn0001 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
