글 읽기 - 어이없는 실수

minkyu4626 2년 전 6

저 같은 경우에는 제출 시에 틀렸다고 나오는데 코드를 다시 보고 아무리 생각해도 로직에 틀린 부분은 없다고 생각했습니다. 그래서 미칠 노릇이었죠. 각 케이스에 대한 방향 설정이 틀렸다는 분들이 많아서 다시 살펴봐도 문제는 없었습니다.

문제는 생각보다 간단한 부분에 존재하더군요. cctv가 하나도 없는 경우에는 min의 값이 map을 counting하는 countArea 함수가 call 되어 설정되어야 하는데 이 부분이 없어 min이 초기 설정값인 N*M 으로 나오더군요.

'모든 반례를 다 돌려보고 맞는데 왜 자꾸 틀렸다고 하지?' 라고 하는 경우에는 의외로 간단하고 기본적인 부분에서의 예외처리에 대한 실수가 많더군요.(제 기준입니다.)

코드는 거짓말하지 않다는 걸 다시 한 번 느끼게 됩니다. 저와 비슷한 문제를 겪으신 분들이 계시다면 글을 읽고 도움이 되셨으면 좋겠습니다!! 화이팅입니다

ps) 그리고 제 답은 코드 중복도 많고 클린코드는 아닌 것 같아서 개선점 조언해주시면 정말 감사하겠습니다.

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

class Main {
    static int N, M;
    static ArrayList<int[]> cctvs;
    static int[][] rooms_origin;
    static int[][] rooms_copy;
    static int min;
    public static void main(String[] args) throws IOException {
        getInput();
        if (cctvs.size() != 0)
            check(0, rooms_origin);
        System.out.println(min);
    }

    private static void check(int cctvNum, int[][] rooms) {

        int[][] roomsTemp = new int[N][M];
        copy(rooms, roomsTemp);
        int x = cctvs.get(cctvNum)[0];
        int y = cctvs.get(cctvNum)[1];
        int cctvType = rooms_origin[x][y];
        for (int i = 0; i < 4; i++) { // 가능한 네 방향의 case에 대해서 탐색
            fillRooms(roomsTemp, cctvType, i, x, y);
            if (cctvNum == cctvs.size() -1) { // 최대 depth, 즉 설치된 cctv 중 마지막 것일 경우
                countArea(roomsTemp);
            }
            for (int j = cctvNum+1; j < cctvs.size(); j++) {
                check(j, roomsTemp);
            }
            copy(rooms, roomsTemp); // 원복 (backtracking)
        }
    }

    private static void countArea(int[][] room) {
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (room[i][j] == 0)
                    cnt++;
            }
        }
        min = Math.min(min, cnt);
    }

    private static void right(int[][] room, int x, int y) {
        for (int C = y + 1; C < M; C++)
            if (room[x][C] == 6) return;
            else if (room[x][C] != 0) continue;
            else room[x][C] = -1;
    }

    private static void down(int[][] room, int x, int y) {
        for (int R = x + 1; R < N; R++)
            if (room[R][y] == 6) return;
            else if (room[R][y] != 0) continue;
            else room[R][y] = -1;
    }

    private static void left(int[][] room, int x, int y) {
        for (int C = y - 1; C >= 0; C--)
            if (room[x][C] == 6) return;
            else if (room[x][C] != 0) continue;
            else room[x][C] = -1;
    }

    private static void up(int[][] room, int x, int y) {
        for (int R = x - 1; R >= 0; R--)
            if (room[R][y] == 6) return;
            else if (room[R][y] != 0) continue;
            else room[R][y] = -1;
    }

    private static void fillRooms(int[][] room, int cctvType, int direction, int x, int y) {
        switch (cctvType) {
            case 1: {
                if (direction == 0) {
                    right(room, x, y);
                } else if (direction == 1) {
                    down(room, x, y);
                } else if (direction == 2) {
                    left(room, x, y);
                } else {
                    up(room, x, y);
                }
                break;
            }
            case 2: {
                if (direction == 0 || direction == 2) {
                    right(room, x, y);
                    left(room, x, y);
                } else {
                    up(room, x, y);
                    down(room, x, y);
                }
                break;
            }
            case 3: {
                if (direction == 0) {
                    right(room, x, y);
                    down(room, x, y);
                } else if (direction == 1) {
                    down(room, x, y);
                    left(room, x, y);
                } else if (direction == 2) {
                    left(room, x, y);
                    up(room, x, y);
                } else {
                    up(room, x, y);
                    right(room, x, y);
                }
                break;
            }
            case 4: {
                if (direction == 0) {
                    right(room, x, y);
                    up(room, x, y);
                    down(room, x, y);
                } else if (direction == 1) {
                    right(room, x, y);
                    left(room, x, y);
                    down(room, x, y);
                } else if (direction == 2) {
                    left(room, x, y);
                    up(room, x, y);
                    down(room, x, y);
                } else {
                    right(room, x, y);
                    left(room, x, y);
                    up(room, x, y);
                }
                break;
            }
            case 5: {
                right(room, x, y);
                left(room, x, y);
                up(room, x, y);
                down(room, x, y);
                break;
            }
            default: break;
        }
    }


    private static void copy(int[][] origin, int[][] copy) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++)
                copy[i][j] = origin[i][j];
        }
    }

    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());
        cctvs = new ArrayList<>();
        rooms_origin = new int[N][M];
        min = N*M;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                int locationType = Integer.parseInt(st.nextToken());
                rooms_origin[i][j] = locationType;
                boolean isCCTVArea = locationType != 0 && locationType != 6;
                if (isCCTVArea) {
                    cctvs.add(new int[] {i, j}); // cctv의 좌표정보를 cctvs에 저장
                }
            }
        }

        countArea(rooms_origin); // cctv가 하나도 없는 경우에는 counting을 해주어야 하는데
                                 // 그냥 N*M을 min으로 설정하는 실수를 범했다. 이 라인을 추가하여 해결하였다.
    }
}

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

문제

문제

출처

ICPC

어이없는 실수

minkyu4626 2년 전 6

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말