[BOJ/Java] 15683. 감시

[BOJ/Java] 15683. 감시

15683번: 감시

---

문제 해석

이 문제는 CCTV가 설치된 감시 시스템을 통해 주어진 사무실의 블라인드 스팟(사각지대)의 최소 영역을 구하는 시뮬레이션 문제다. 각 CCTV는 특정 방향으로만 감시할 수 있으며, 각 CCTV의 종류에 따라 감시할 수 있는 방향이 정해져 있다. 목표는 모든 CCTV의 방향을 조정하여 사각지대의 면적을 최소화하는 것이다.

풀이 과정

1. 입력을 받아 사무실의 크기, 각 칸의 상태, 그리고 CCTV의 위치와 종류를 저장한다.
2. 각 CCTV를 회전시켜 가능한 모든 방향을 탐색하며, 각 설정에 대해 사각지대의 크기를 계산한다.
3. DFS(깊이 우선 탐색)를 사용하여 모든 CCTV의 모든 가능한 방향 조합을 탐색한다.
4. 각 CCTV에 대해 정해진 방향에 따라 감시 영역을 표시하고, 감시되는 영역을 확장한다.
5. 모든 CCTV에 대한 방향 설정이 완료된 후, 감시되지 않는 영역(사각지대)의 크기를 계산한다.
6. 가능한 모든 조합 중 사각지대가 가장 작은 경우를 찾아 출력한다.

코드

package edu.ssafy.im.BOJ.Gold.G4.No15683;

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 {
    public static void main(String[] args) throws IOException {
        new Main().sol();
    }

    private int n;  // 사무실 세로 크기
    private int m;  // 사무실 가로 크기
    private int[][] map;  // 사무실 지도
    private List<Point> cctvList;  // CCTV 리스트
    private int ans = Integer.MAX_VALUE;  // 사각 지대의 최소 크기
    private static final int[][] direction = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };  // 감시 방향 (동, 남, 서, 북)

    class Point {
        int x, y, type;

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

    private void sol() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        cctvList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] != 0 && map[i][j] != 6)
                    cctvList.add(new Point(i, j, map[i][j]));
            }
        }

        dfs(0);  // 모든 CCTV에 대해 가능한 모든 방향 조합을 탐색

        sb.append(ans);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private void dfs(int idx) {
        if (idx == cctvList.size()) {
            ans = Math.min(ans, getAns());  // 사각지대 계산 후 최소값 업데이트
            return;
        }

        Point p = cctvList.get(idx);
        
        int[][] tmp = new int[n][m];
        for (int d = 0; d < direction.length; d++) {
            tmp = copy(map);  // 현재 상태 복사
            switch (p.type) {
            case 1:  // 1번 CCTV
                go(p, d);
                dfs(idx + 1);
                break;
            case 2:  // 2번 CCTV
                go(p, d);
                go(p, (d + 2) % 4);
                dfs(idx + 1);
                break;
            case 3:  // 3번 CCTV
                go(p, d);
                go(p, (d + 1) % 4);
                dfs(idx + 1);
                break;
            case 4:  // 4번 CCTV
                go(p, d);
                go(p, (d + 1) % 4);
                go(p, (d + 3) % 4);
                dfs(idx + 1);
                break;
            case 5:  // 5번 CCTV
                for (int i = 0; i < direction.length; i++) {
                    go(p, (d + i) % 4);
                }
                dfs(idx + 1);
                break;
            }
            map = copy(tmp);  // 원래 상태로 복구
            if (p.type == 2)
                d += 1;
            if (p.type == 5)
                break;
        }
    }

    private int[][] copy(int[][] map) {  // 맵 복사 함수
        int[][] tmp = new int[n][m];
        for (int i = 0; i < n; i++) {
            tmp[i] = map[i].clone();
        }
        return tmp;
    }

    private void go(Point p, int d) {  // CCTV 감시 영역 확장 함수
        int nx = p.x + direction[d][0];
        int ny = p.y + direction[d][1];

        if (nx < 0 || ny < 0 || nx >= n || ny >= m || map[nx][ny] == 6)
            return;
        if (map[nx][ny] != 0)
            go(new Point(nx, ny, p.type), d);
        if (map[nx][ny] == 0) {
            map[nx][ny] = p.type;
            go(new Point(nx, ny, p.type), d);
        }
    }

    private int getAns() {  // 사각지대 크기 계산 함수
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0)
                    cnt++;
            }
        }
        return cnt;
    }
}

시간 복잡도 분석

이 알고리즘은 모든 CCTV의 모든 방향 조합을 검토해야 하므로, 각 CCTV에 대해 가능한 모든 방향 설정을 고려하는 복잡한 과정을 포함한다. 최악의 경우, 각 CCTV에 대해 여러 방향을 시험해보아야 하며, 이는 상당한 계산 시간을 요구할 수 있다.

느낀점

이 문제는 DFS를 통한 완전 탐색 문제로, 각 CCTV의 방향을 설정하는 모든 경우의 수를 고려해야 한다. 이를 통해 사각지대의 최소 면적을 찾는 것이 핵심 도전 과제로, 효율적인 탐색과 상태 관리가 중요한 역할을 한다.