[백준/JAVA] 15683번: 감시

📖 문제

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

 

 

💡  풀이 방식

• 시뮬레이션 + 백트래킹 + 브루트포스

 

•  각 CCTV의 타입을 받아, 각 타입에 맞춰 회전된 상태를 조합해 사각지대의 최소값을 구한다.
  • CCTV 타입이 1( → )인 경우 : 북(0 / ↑), 남(1 / ↓), 서(2 / ←), 동(3 / →)
  • CCTV 타입이 2( ↔ )인 경우 : 서동(23 / ↔), 북남(01 / ↕ )
  • CCTV 타입이 3(↑→)인 경우 : 북동(03 / ↑→) , 남동(13 / ↓→) , 남서(12 / ↓←) , 북서(02 / ←↑)
  • CCTV 타입이 4( ←↑→ )인 경우 : 북서동(023), 북남동(013), 남서동(123), 북남서 (012)
  • CCTV 타입이 5(↕↔)인 경우 : 북남서동(0123 /  ↕↔ )

static int[][][] mode = {{{0}},
                         {{0}, {1}, {2}, {3}},                  // CCTV 타입이 1인 경우
                         {{2,3}, {0,1}},                        // CCTV 타입이 2인 경우
                         {{0,3}, {1,3}, {1,2}, {0,2}},          // CCTV 타입이 3인 경우
                         {{0,2,3}, {0,1,3}, {1,2,3}, {0,1,2}},  // CCTV 타입이 4인 경우
                         {{0,1,2,3}}};                          // CCTV 타입이 5인 경우

 

 

• 각 CCTV가 있는 위치와 타입을 CCTV 객체 리스트에 저장한다.
• 그 후, 조합으로 각 cctv마다 특정 경우 조합으로 감시했을 때의 사각지대를 구한 후, 이를 최솟값과 비교하며 사각지대를 최솟값으로 갱신한다.

private static void dfs(int depth, int[][] map) {
    // cctv 다 선택해봤을 때 결과 출력
    if(depth == list.size()) {
        answer = Math.min(answer, check(map));
        return;
    }

    CCTV now = list.get(depth);
    int num = now.num;
    int r = now.r;
    int c = now.c;

    for(int i = 0 ; i < mode[num].length ; i++) {
        // 배열 복사하기
        int[][] copy = new int[N][M];
        for(int a = 0 ; a < N ; a++) {
            for(int b = 0 ; b < M ; b++)
                copy[a][b] = map[a][b];
        }

        for(int j = 0 ; j < mode[num][i].length ; j++) {
            int dir = mode[num][i][j];  // 현재 방향

            int nr = r + dr[dir];
            int nc = c + dc[dir];

            // 격자 범위 벗어나거나, 벽(6)에 닿기 전까지 현재 방향으로 계속 이동
            while(true) {
                if(nr < 0 || nr >= N || nc < 0 || nc >= M)  break;
                if(map[nr][nc] == 6)    break;

                copy[nr][nc] = -1;  // 방문 표시
                nr += dr[dir];
                nc += dc[dir];
            }
        }

        dfs(depth + 1, copy);
    }
}

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dr = {-1,1,0,0};   // 북남서동
    static int[] dc = {0,0,-1,1};
    
    // 90도로 회전할 수 있는 경우의 수
    static int[][][] mode = {{{0}},
                             {{0}, {1}, {2}, {3}},                  // CCTV 타입이 1인 경우
                             {{2,3}, {0,1}},                        // CCTV 타입이 2인 경우
                             {{0,3}, {1,3}, {1,2}, {0,2}},          // CCTV 타입이 3인 경우
                             {{0,2,3}, {0,1,3}, {1,2,3}, {0,1,2}},  // CCTV 타입이 4인 경우
                             {{0,1,2,3}}};                          // CCTV 타입이 5인 경우
    
    static int N,M, answer;
    static int[][] map;
    static int zeroCnt = 0;
    
    static List<CCTV> list = new ArrayList<>(); // CCTV 위치 저장 리스트
    
    public static void main(String[] args) 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());   // 가로
        
        map = new int[N][M];
        
        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)
                    zeroCnt++;
                else if(map[i][j] >= 1 && map[i][j] <= 5)
                    list.add(new CCTV(i, j, map[i][j]));
            }
        }
        
        answer = zeroCnt;
        dfs(0, map);
        System.out.println(answer);
    }
    
    // 각 cctv마다 특정 경우에 조합으로 감시했을 때 사각지대가 얼마인지 구하는 메소드
    private static void dfs(int depth, int[][] map) {
        // 모든 cctv를 다 확인해봤다면, 사각지대의 최소값 갱신
        if(depth == list.size()) {
            answer = Math.min(answer, check(map));
            return;
        }
        
        CCTV now = list.get(depth);
        int num = now.num;
        int r = now.r;
        int c = now.c;
        
        for(int i = 0 ; i < mode[num].length ; i++) {
            // 배열 복사하기
            int[][] copy = new int[N][M];
            for(int a = 0 ; a < N ; a++) {
                for(int b = 0 ; b < M ; b++)
                    copy[a][b] = map[a][b];
            }
            
            for(int j = 0 ; j < mode[num][i].length ; j++) {
                int dir = mode[num][i][j];  // 현재 방향
                
                int nr = r + dr[dir];
                int nc = c + dc[dir];
                
                // 격자 범위 벗어나거나, 벽(6)에 닿기 전까지 현재 방향으로 계속 이동
                while(true) {
                    if(nr < 0 || nr >= N || nc < 0 || nc >= M)  break;
                    if(map[nr][nc] == 6)    break;
                    
                    copy[nr][nc] = -1;  // 방문 표시
                    nr += dr[dir];
                    nc += dc[dir];
                }
            }
            
            dfs(depth + 1, copy);
        }
    }
    
    // 사각지대(0) 구하는 메소드
    private static int check(int[][] map) {
        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;
    }
}
 
class CCTV {
    int r, c, num;
    
    public CCTV(int r, int c, int num) {
        this.r = r;
        this.c = c;
        this.num = num;
    }
}

 

 

➕ 다른 풀이 방식

- 왼쪽,오른쪽,위,아래 방향을 탐색하는 함수를 별도로 만들어 푸셨다.

[백준]15683: 감시(java)

 

 

- 개인적으로 이게 조금 더 깔끔하고 가독성 좋은 것 같다. ✅

백준 / 백트래킹 / 15683번 / 감시 / Java

 

 

- BFS를 활용한 풀이

[백준 - Java] 15683번 : 감시 (삼성 SW 역량 테스트 기출 문제)

---

💦 어려웠던 점

- 어떻게 일일이 타입마다 회전을 시키지?의 문제

 

 

🧐 새로 알게 된 내용

- 함수 파라미터로 값 변경된 배열을 들고 가서 활용하는 것,,, 그럼 원본 배열을 수정하고 복구하고 이런 과정을 하지 않아도 된다...

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 참고

BOJ - 감시 15683번 (Java)