백준 15683 감시 (java)

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

 

처음 풀었던 전략 : 그리디

1. 각 카메라 위치를 리스트에 넣어두고

2. 카메라 하나씩 처리 -> 카메라 유형에 따라 가능한 경우의수중 사각지대를 제일 많이 없애는 방향 구하기

3. 카메라 감시 처리 -> 해당 방향으로 카메라가 감시한 영역을 -1로 설정

 

매 카메라마다 가장 많이 사각지대를 지우는 방향의 로직이었는데,

지금 카메라가 최적의 수를 포기하더라도 다음 카메라가 어떻게 잘 관제해주면 더 좋은 합이 나올 수 있었음 << 그래서 틀림

 

결국 모든 카메라 조합에 대해 완전탐색을 해야했고, << 카메라 개수가 8개까지 제한이 걸린거로 눈치를 챘을 수도 있을 것 같다.

 

시간 절약을 위해 백트래킹을 사용해야 하는 문제.

 

dfs로 1번카메라 방향설정 -> 2, 3, 4, 5, 6 설정후 마지막 카메라까지 설정했다면 해당 케이스의 사각지대 계산, 이후 return

 

그럼 마지막 카메라 경우 하나가 방향이 바뀐 케이스가 다음 케이스니까 사각지대 계산, 이후 return

 

이런 식으로 백트래킹을 하기 위해 매 dfs마다 board를 복사해서 각 케이스마다 다른 board를 사용하도록 해줘야한다. 그게 copyBoard 메서드다.

안그럼 다른케이스끼리 서로 같은 board 건드리고 난리난다. java에선 clone을 썼는데 파이썬이라면 어떻게 전달해야할까?

 

import java.io.*;
import java.util.*;

public class bj_15683_감시 {
    static int n, m;
    static int[][] board;
    // 0 : 동 1 : 남 2 :서 3 : 북
    static int[][][] mode = {
            {},
            {{0}, {1}, {2}, {3}},
            {{0, 2}, {1, 3}},
            {{0, 3}, {0, 1}, {1, 2}, {2, 3}},
            {{0, 2, 3}, {0, 1, 3}, {0, 1, 2}, {1, 2, 3}},
            {{0, 1, 2, 3}}
    };
    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0};
    static List<int[]> camera;
    static int answer = Integer.MAX_VALUE;
    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());

        board = new int[n][m];
        camera = new ArrayList<>();

        for(int i = 0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<m; j++){
                board[i][j] = Integer.parseInt(st.nextToken());

                if(board[i][j] >= 1 && board[i][j] < 6){
                    camera.add(new int[] {i, j, board[i][j]});
                }
            }
        }

        dfs(0, board);
        System.out.print(answer);
    }

    static void dfs(int index, int[][] prevBoard){
        if (index == camera.size()){
            answer = Math.min(answer, count_spot(prevBoard));
            return;
        }

        int r = camera.get(index)[0];
        int c = camera.get(index)[1];
        int type = camera.get(index)[2];

        for (int i = 0; i < mode[type].length; i++){
            int[][] nextBoard = copyBoard(prevBoard);

            for (int d : mode[type][i]){
                fill(r, c, d, nextBoard);
            }

            dfs(index + 1, nextBoard);
        }
    }

    static void fill(int r, int c, int direction, int[][] tempBoard){
        int nr = r + dr[direction];
        int nc = c + dc[direction];
        while(0 <= nr && nr < n &&  0 <= nc && nc < m && tempBoard[nr][nc] != 6){
            if (tempBoard[nr][nc] == 0) tempBoard[nr][nc] = -1;
            nr += dr[direction];
            nc += dc[direction];
        }

    }

    static int[][] copyBoard(int[][] original){
        int[][] copy = new int[n][m];
        for(int i = 0; i<n; i++){
            copy[i] = original[i].clone();
        }
        return copy;
    }

    static int count_spot(int[][] tempBoard){
        int count = 0;
        for(int i = 0; i< n; i++){
            for (int j = 0; j < m; j++)
                if (tempBoard[i][j] == 0) count++;
        }
        return count;
    }
}

 

구현 문제는 케이스 지킨다고 시간도 오래걸려서

 

열심히 풀었는데 처음부터 접근이 잘못된 경우일 때 너무 허무한 것 같다.