백준 15683. 감시 :: 돼지개발자

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

"구현, 브루트 포스"

아래와 같이 구현했다. 삼성 기출 문제. 특정 위치에 있는 CCTV가 종류별로 있는데, 이를 4방향으로 돌려가며

사각지대 0의 개수를 최소로 줄이는 경우를 찾는 것이다. 아래 풀이에서는 각 CCTV 마다 한 방향만을 설정해주었는데, 회전 가능한 4방향에 대해서 다 정의해 준다면,  2번 CCTV 는 2회, 5번 CCTV는 1회로 횟수를 더욱 줄일 수 있다.

근데 나는 귀찮아서 그냥 4방향 다 돌렸따....

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    static int N,M;
    static int cnt;
    static int min = Integer.MAX_VALUE;
    static Node[] nodes = new Node[8];
    static int[][] dir = {
        {},
        {1},
        {1,3},
        {0,1},
        {0,1,3},
        {0,1,2,3}
    };
    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,1,0,-1};
    
    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());
        
        int[][] 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] >= 1 && map[i][j] <= 5) {
                    nodes[cnt++] = new Node(i, j, map[i][j]);
                }
            }
        }
        
        solve(0, map);
        System.out.println(min);
    }
    
    static void solve(int idx, int[][] arr) {
        if(idx == cnt) {
            int res = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if(arr[i][j] == 0)
                        res++;
                }
            }
            min = Math.min(min, res);
            return ;
        }
        Node node = nodes[idx];
        
        // 왼쪽으로 4번 돌린다.
        for (int d = 0; d < 4; d++) {
            int[][] map = copy(arr);
            
            // 해당 CCTV가 감시하는 모든 방향에 대해 체크 한다.
            // 1,2,3,4  방향이 될 수 있다.
            for (int i = 0; i < dir[node.c].length; i++) {
                int nd = (dir[node.c][i]-d + 3) % 4;
                int nx = node.x;
                int ny = node.y;
                
                while(true) {
                    nx += dx[nd];
                    ny += dy[nd];
                    if(!isRange(nx, ny) || map[nx][ny] == 6) break;
                    map[nx][ny] = 7;
                }
            }
            solve(idx+1, map);
        }
    }
    
    static boolean isRange(int x, int y) {
        if(x < 0 || x >= N || y < 0 || y >= M) return false;
        return true;
    }
    
    static int[][] copy(int[][] arr) {
        int[][] map = new int[N][M];
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                map[i][j] = arr[i][j];
            }
        }
        return map;
    }
}
 
class Node {
    int x;
    int y;    
    int c;    // cctv
    
    Node (int x, int y, int c) {
        this.x = x;
        this.y = y;
        this.c = c;
    }
}