글 읽기 - dfs로 문제를 푸는데 4%에서 자꾸 실패를 합니다.

ksch123200 6년 전 0

dfs로 문제를 푸는데 4%에서 자꾸 실패를 합니다.

일단 제가 테스트 해본 것은 문제에서 나온 테스트 케이스와 질문 게시판에 있는 테스트 케이스 입니다. 혹시 반례가 있으시면 알려주시면 감사하겠습니다.

import java.util.Scanner;

public class Main {
    static int N, M, max = 11;
    static char map[][];

    public static void main(String[] args) {
        int redX = 0, redY = 0, blueX = 0, blueY = 0;
        Main main = new Main();

        Scanner scan = new Scanner(System.in);
        N = scan.nextInt();
        M = scan.nextInt();

        map = new char[N][M];

        scan.nextLine();
        for (int i = 0; i < N; i++) {
            String str = scan.nextLine();
            for (int j = 0; j < M; j++) {
                char gettingChar = str.charAt(j);
                map[i][j] = gettingChar;
                if (gettingChar == 'R') {
                    redX = i;
                    redY = j;
                    map[i][j] = '.';
                } else if (gettingChar == 'B') {
                    blueX = i;
                    blueY = j;
                    map[i][j] = '.';
                }
            }
        }

        char a = 'a' - 45;

        main.moveBall(redX, redY, blueX, blueY, -1, 0);

        if (max > 10) {
            System.out.println(-1);
        } else {
            System.out.println(max);
        }
    }

    private void moveBall(int redX, int redY, int blueX, int blueY, int direction, int count) {
        int changeRedX, changeRedY, changeBlueX, changeBlueY;

        if (map[blueX][blueY] == 'O') {
            return;
        }

        if (map[redX][redY] == 'O') {
            if(checkBlueBall(blueX, blueY, direction) && count < max){
                max = count;
            }
            return;
        }

        if (count >= max) {
            return;
        }

        changeBlueX = moveUp(redX, redY, blueX, blueY, map);
        changeRedX = moveUp(blueX, blueY, redX, redY, map);
        if (direction == 0 && (changeBlueX != blueX || changeRedX != redX)) {
            moveBall(changeRedX, redY, changeBlueX, blueY, 0, count);
        } else if (direction != 0 && (changeBlueX != blueX || changeRedX != redX)) {
            moveBall(changeRedX, redY, changeBlueX, blueY, 0, count + 1);
        }

        changeBlueX = moveDown(redX, redY, blueX, blueY, map);
        changeRedX = moveDown(blueX, blueY, redX, redY, map);
        if (direction == 1 && (changeBlueX != blueX || changeRedX != redX)) {
            moveBall(changeRedX, redY, changeBlueX, blueY, 1, count);
        } else if (direction != 1 && (changeBlueX != blueX || changeRedX != redX)) {
            moveBall(changeRedX, redY, changeBlueX, blueY, 1, count + 1);
        }

        changeBlueY = moveLeft(redX, redY, blueX, blueY, map);
        changeRedY = moveLeft(blueX, blueY, redX, redY, map);
        if (direction == 2 && (changeBlueY != blueY || changeRedY != redY)) {
            moveBall(redX, changeRedY, blueX, changeBlueY, 2, count);
        } else if (direction != 2 && (changeBlueY != blueY || changeRedY != redY)) {
            moveBall(redX, changeRedY, blueX, changeBlueY, 2, count + 1);
        }

        changeBlueY = moveRight(redX, redY, blueX, blueY, map);
        changeRedY = moveRight(blueX, blueY, redX, redY, map);
        if (direction == 3 && (changeBlueY != blueY || changeRedY != redY)) {
            moveBall(redX, changeRedY, blueX, changeBlueY, 3, count);
        } else if (direction != 3 && (changeBlueY != blueY || changeRedY != redY)) {
            moveBall(redX, changeRedY, blueX, changeBlueY, 3, count + 1);
        }
    }

    private int moveUp(int compareX, int compareY, int x, int y, char map[][]) {
        for (int i = x - 1; i > 0; i--) {
            if ((compareX == i && compareY == y) || map[i][y] == '#') {
                break;
            }
            if (map[i][y] == '.' || map[i][y] == 'O') {
                x--;
                if (map[i][y] == 'O')
                    break;
            }
        }

        return x;
    }

    private int moveDown(int compareX, int compareY, int x, int y, char map[][]) {
        for (int i = x + 1; i < N; i++) {
            if ((compareX == i && compareY == y) || map[i][y] == '#') {
                break;
            }
            if (map[i][y] == '.' || map[i][y] == 'O') {
                x++;
                if (map[i][y] == 'O')
                    break;
            }
        }

        return x;
    }

    private int moveLeft(int compareX, int compareY, int x, int y, char map[][]) {
        for (int i = y - 1; i > 0; i--) {
            if ((compareX == x && compareY == i) || map[x][i] == '#') {
                break;
            }
            if (map[x][i] == '.' || map[x][i] == 'O') {
                y--;
                if (map[x][i] == 'O')
                    break;
            }
        }

        return y;
    }

    private int moveRight(int compareX, int compareY, int x, int y, char map[][]) {
        for (int i = y + 1; i < M; i++) {
            if ((compareX == x && compareY == i) || map[x][i] == '#') {
                break;
            }
            if (map[x][i] == '.' || map[x][i] == 'O') {
                y++;
                if (map[x][i] == 'O')
                    break;
            }
        }

        return y;
    }

    private boolean checkBlueBall(int x, int y, int direction) {
        switch (direction) {
            case 0:
                if (x - 1 > 0 && map[x - 1][y] == '.') {
                    return checkBlueBall(x - 1, y, direction);
                } else if (x - 1 > 0 && map[x - 1][y] == 'O') {
                    return false;
                } else {
                    return true;
                }
            case 1:
                if (x + 1 < N - 1 && map[x + 1][y] == '.') {
                    return checkBlueBall(x + 1, y, direction);
                } else if (x + 1 < N - 1 && map[x + 1][y] == 'O') {
                    return false;
                } else {
                    return true;
                }
            case 2:
                if (y - 1 > 0 && map[x][y - 1] == '.') {
                    return checkBlueBall(x, y - 1, direction);
                } else if (y - 1 > 0 && map[x][y - 1] == 'O') {
                    return false;
                } else {
                    return true;
                }
            case 3:
                if (y + 1 < M - 1 && map[x][y + 1] == '.') {
                    return checkBlueBall(x, y + 1, direction);
                } else if (y + 1 < M - 1 && map[x][y + 1] == 'O') {
                    return false;
                } else {
                    return true;
                }
        }

        return true;
    }

}

sorrly 6년 전 0

저도 같은 문제를 겪고 있는데요.

혹시 어떻게 해결하셨는지..

알려주실 수 있을까요??

저도 dfs 로 풀었는데..ㅠㅠ

안되네요..ㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

dfs로 문제를 푸는데 4%에서 자꾸 실패를 합니다.

ksch123200 6년 전 0

sorrly 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말