[BOJ] 15683. 감시

https://www.acmicpc.net/problem/15683

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main_15683_감시 {
    static int N, M;
    static int[][] room;
    static int result = Integer.MAX_VALUE;
    static int[] dx = { -1, 1, 0, 0 }; // 상하좌우
    static int[] dy = { 0, 0, -1, 1 };
    static ArrayList<Point> cctvList = new ArrayList<>();

    static class Point {
        int x;
        int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        st = new StringTokenizer(in.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        room = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(in.readLine());
            for (int j = 0; j < M; j++) {
                room[i][j] = Integer.parseInt(st.nextToken());
                if (room[i][j] != 0 && room[i][j] != 6) {
                    cctvList.add(new Point(i, j));
                }
            }
        }

        dfs(0);

        sb.append(result);
        out.write(sb.toString());
        out.flush();
        out.close();
    }

    private static void dfs(int idx) {
        if (idx == cctvList.size()) {
            result = Math.min(result, blindSpot());
            return;
        }
        Point cctv = cctvList.get(idx);
        int x = cctv.x;
        int y = cctv.y;

        List<List<Point>> watchList = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            watchList.add(new ArrayList<>());
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            while (nx >= 0 && ny >= 0 && nx < N && ny < M && room[nx][ny] != 6) {
                if (room[nx][ny] == 0) {
                    watchList.get(i).add(new Point(nx, ny));
                }
                nx += dx[i];
                ny += dy[i];

            }
        } // 4방향으로 볼 수 있는 모든 좌표 리스트에 저장

        if (room[x][y] == 1) {
            for (int i = 0; i < 4; i++) {
                changeRoom(watchList.get(i), -1);
                dfs(idx + 1);
                changeRoom(watchList.get(i), 0);
            }
        } else if (room[x][y] == 2) {
            for (int i = 0; i < 3; i += 2) {
                changeRoom(watchList.get(i), -1);
                changeRoom(watchList.get(i + 1), -1);
                dfs(idx + 1);
                changeRoom(watchList.get(i), 0);
                changeRoom(watchList.get(i + 1), 0);
            }
        } else if (room[x][y] == 3) {
            for (int i = 0; i < 2; i++) {
                changeRoom(watchList.get(i), -1);
                for (int j = 2; j < 4; j++) {
                    changeRoom(watchList.get(j), -1);
                    dfs(idx + 1);
                    changeRoom(watchList.get(j), 0);
                }
                changeRoom(watchList.get(i), 0);
            }

        } else if (room[x][y] == 4) {
            for (int i = 0; i < 4; i++) {
                changeRoom(watchList.get(i), -1);
                changeRoom(watchList.get((i + 1) % 4), -1);
                changeRoom(watchList.get((i + 2) % 4), -1);
                dfs(idx + 1);
                changeRoom(watchList.get(i), 0);
                changeRoom(watchList.get((i + 1) % 4), 0);
                changeRoom(watchList.get((i + 2) % 4), 0);
            }

        } else {
            for (int i = 0; i < 4; i++) {
                changeRoom(watchList.get(i), -1);
            }
            dfs(idx + 1);
            for (int i = 0; i < 4; i++) {
                changeRoom(watchList.get(i), 0);
            }

        }

    }

    private static int blindSpot() { // 사각지대
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {

                if (room[i][j] == 0) {
                    cnt++;
                }
            }

        }

        return cnt;
    }

    private static void changeRoom(List<Point> watchList, int val) {

        for (int i = 0; i < watchList.size(); i++) {
            Point cur = watchList.get(i);
            room[cur.x][cur.y] = val;
        }
    }

}

• 4방향으로 볼 수 있는 모든 좌표를 큐에 저장했었는데 리스트로 변경함.
  • changeRoom에서 큐에서 값을 빼면서 room배열을 -1로 업데이트 해주고 다시 0으로 되돌려주려고 했는데 0으로 되돌아가지 않는 문제가 발생함.
  • 이유는 큐를 여러 메소드에서 사용할 때 파라미터로 보낸 큐에서 요소를 삭제하면 원본 큐에도 영향을 미치기 때문이다.
    • 기본 자료형 변수가 파라미터로 넘겨지면 값을 넘기지만, Array, List 등의 변수가 파라미터로 넘겨지면 주소를 넘긴다.
• 사각지대 개수 세는 메소드와 같이 간단한 메소드들을 처음부터 시간복잡도를 고려해서 풀려고 하는 경향이 있는데 이것때문에 생각이 더 복잡해짐. 간단한 메소드들은 나중에 최적화해줘도 되니까 간단하게 생각하는 연습하기.
• 한 지점에서 4방향으로 볼 수 있는 모든 좌표 구하는 방법 익히기
• cctv type에 따라 처리하는 법 익히기
  • 좌표를 수식으로 처리하는 것
  • 먼저 모든 방향에 대해 볼 수 있는 좌표 구하고 이를 각 상황에 맞게 메소드에 파라미터 값으로 넣어줘서 코드의 가독성 높히기