글 읽기 - 26% 에서 실패

minkyu4626 2년 전 0

게시판에 보이는 모든 반례들을 확인하였고

항상 테두리는 모두 1이기에 범위 밖을 벗어나는 경우는 없다는 것도 알고 canCleanArea() 도 이점 고려해서 작성했습니다.

dfs를 통해 접근하였고 아무리 코드를 살펴봐도 문제점이 보이지 않아 다른 분들에게는 보이지 않을까 싶어 질문글 남깁니다. 답변해주시면 정말 감사드리겠습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {
    static int N, M;
    static int[][] room;
    static int[] x_dir = {-1, 0, 1, 0}; // 위 왼 아래 오른 순
    static int[] y_dir = {0, -1, 0, 1};
    static boolean[][] isCleaned;
    static int X, Y;
    static int direction;
    static int cleanCnt = 0;
    public static void main(String[] args) throws Exception {
        getInput();
        int cur_x = X;
        int cur_y = Y;
        isCleaned = new boolean[N][M];

        clean(cur_x, cur_y);

        System.out.printf("%d", cleanCnt);
    }

    private static void clean(int cur_x, int cur_y) {
        if (!isCleaned[cur_x][cur_y]) {
            isCleaned[cur_x][cur_y] = true;
            cleanCnt++;
        }

        for (int i = 0; i < 4; i++) { // 네 방향에 대해 확인
            direction = getNextDirection(direction);
            int next_x = cur_x + x_dir[direction];
            int next_y = cur_y + y_dir[direction];
            if (canCleanArea(next_x, next_y)) {
                direction = direction;
                clean(next_x, next_y);
                return;
            }
        }

        if (canBack(cur_x,cur_y)) { // 후진이 가능한 경우
            int next_x = cur_x + x_dir[(direction+2)%4];
            int next_y = cur_y + y_dir[(direction+2)%4];
            clean(next_x, next_y);
        }

    }

    private static void getInput() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        X = Integer.parseInt(st.nextToken());;
        Y = Integer.parseInt(st.nextToken());;
        direction = Integer.parseInt(st.nextToken());
        if (direction == 1) direction = 3;
        else if (direction == 3) direction = 1;
        room = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++)
                room[i][j] = Integer.parseInt(st.nextToken());
        }
    }

    static private int getNextDirection(int direction) {
        return (direction+1) % 4;
    }

    static private boolean canCleanArea(int x, int y) {
        if (room[x][y] == 1)
            return false;
        if (isCleaned[x][y])
            return false;
        return true;
    }
    static private boolean canBack(int x, int y) {
        x = x + x_dir[(direction+2)%4];
        y = y + y_dir[(direction+2)%4];

        if (x >= N || x < 0 || y >= N || y < 0)
            return false;
        if (room[x][y] == 1)
            return false;
        return true;
    }


}

kdh6429 2년 전 1

방향정보를 가지는 dir 배열 순서가 맞는지 궁금합니다.

minkyu4626 2년 전 0

dir 배열의 순서는 up, left, down right 순서입니다.

따라서 60-61 번 라인
60: if (direction == 1) direction = 3;
61: else if (direction == 3) direction = 1;

이렇게 입력과 dir 배열간의 차이를 수정해주었습니다. 다른 부분이 문제인 것 같은데 혹시 아실련지요?

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

문제

문제

출처

ICPC

26% 에서 실패

minkyu4626 2년 전 0

kdh6429 2년 전 1

minkyu4626 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말