BOJ15683_감시

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

문제정리

1. cctv의 종류는 5가지 1: 오른쪽 감시 , 2 : 오른쪽 왼쪽 감시 , 3 : 위 오른쪽 감시 , 4 : 위 오른쪽 왼쪽 감시 , 5 : 위 아래 오른쪽 왼쪽 감시

2. cctv는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다 , 벽은 통과할 수 없고 벽은 6이다

3. cctv는 회전시킬 수 있는데 , 회전은 항상 90도 방향으로 해야 하며 , 감시하려고 하는 방향이 가로 또는 세로 방향 이어야 한다

4. cctv는 다른 cctv를 통과할 수 있다

5. 사무실의 크기와 상태 , cctv정보가 주어졌을 때 , cctv의 방향을 적절히 정해서 사각 지대의 최소크기를 구하는 프로그램을 작성

6. cctv의 최대 개수는 8개를 넘지 않는다

문제issue

cctv 돌리는 부분

1. map에서 cctv 개수를 파악해서 배열을 생성한다

2. 배열에 cctv의 위치와 cctv의 번호를 저장한다

3. [0,1,2,3] 인 배열로 cctv 개수만큼 중복순열 돌려서 돌리는 모든 경우를 다 본다

4. 0은 안돌림 , 1은 한번 돌림 , 2는 2번 돌림 , 3은 3번 돌림

5. 돌린 후 현재 cctv 위치를 기준으로 map_clone에서 어느 방향만 감시할지 보고 감시하는 방향으로만 이동하면서 0이면 8로 마킹해준다

6. 범위를 넘어가거나 벽을 만나면 반복을 종료한다

해결흐름

1. 중복순열을 이용해서 몇 번째 cctv를 각각 몇번 돌릴지 결정

2. cctv의 상태에 맞게 map에서 0인 곳을 임의의 숫자 8로 바꿔준다

3. 모든 cctv를 돌고 빈곳 0을 카운트 해준다

4. 최솟값을 도출한다

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
    static class cctv {
        int r;
        int c;
        int number;
 
        public cctv(int r, int c, int number) {
            super();
            this.r = r;
            this.c = c;
            this.number = number;
        }
    }
 
    private static int[] pi_arr = { 0, 1, 2, 3 };
    private static int N;
    private static int M;
    private static int cctv_cnt;
    private static int[] temp_arr;
    private static cctv[] cctv_arr;
    private static int[][] map;
    private static int[][] map_clone;
    private static int min;
    private static int empty_cnt;
 
    public static void main(String[] args) throws Exception {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        map_clone = new int[N][M];
        cctv_cnt = 0;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine().trim(), " ");
            for (int j = 0; j < M; j++) {
                int number = Integer.parseInt(st.nextToken());
                map[i][j] = number;
                map_clone[i][j] = number;
                if (number != 0 && number != 6) {
                    cctv_cnt++;
                }
            }
        }
        // cctv 개수만큼 배열 생성
        cctv_arr = new cctv[cctv_cnt];
        int cctv_idx = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != 0 && map[i][j] != 6) {
                    cctv_arr[cctv_idx++] = new cctv(i, j, map[i][j]);
                }
            }
        }
        // start
        temp_arr = new int[cctv_cnt];
        min = Integer.MAX_VALUE;
        pi(0);
        System.out.println(min);
 
    } // end of main
 
    private static void pi(int len) {
        if (len == cctv_cnt) {
            map_clone = new int[N][M];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    map_clone[i][j] = map[i][j];
                }
            }
            empty_cnt = 0;
            solve();
            if (min > empty_cnt)
                min = empty_cnt;
            return;
        }
        for (int i = 0; i < 4; i++) {
            temp_arr[len] = pi_arr[i];
            pi(len + 1);
        }
    }
 
    private static void solve() {
        // temp_arr에 있는 각각의 cctv를 몇번 돌릴지 나와 있는 그대로 돌려보면서 빈곳 0 을 카운트
        for (int i = 0; i < cctv_cnt; i++) {
            // cctv number로 먼저 구분
            if (cctv_arr[i].number == 1) {
                // 몇 번 돌리는 지로 구분
                if (temp_arr[i] == 0) {
                    // 현재 cctv위치를 기준으로 map_clone에서 오른쪽만 감시
                    right(i);
                } else if (temp_arr[i] == 1) {
                    // 아래만 감시
                    down(i);
                } else if (temp_arr[i] == 2) {
                    // 왼쪽만 감시
                    left(i);
                } else if (temp_arr[i] == 3) {
                    // 위만 감시
                    up(i);
                }
            } else if (cctv_arr[i].number == 2) {
                if (temp_arr[i] == 0 || temp_arr[i] == 2) {
                    // 오른쪽 , 왼쪽 감시
                    right(i);
                    left(i);
                } else if (temp_arr[i] == 1 || temp_arr[i] == 3) {
                    // 위 , 아래 감시
                    up(i);
                    down(i);
                }
            } else if (cctv_arr[i].number == 3) {
                if (temp_arr[i] == 0) {
                    // 위 , 오른쪽 감시
                    up(i);
                    right(i);
                } else if (temp_arr[i] == 1) {
                    // 아래 , 오른쪽 감시
                    down(i);
                    right(i);
                } else if (temp_arr[i] == 2) {
                    // 아래 , 왼쪽 감시
                    down(i);
                    left(i);
                } else if (temp_arr[i] == 3) {
                    // 위 , 왼쪽 감시
                    up(i);
                    left(i);
                }
            } else if (cctv_arr[i].number == 4) {
                if (temp_arr[i] == 0) {
                    // 위 , 오른쪽 , 왼쪽 감시
                    up(i);
                    right(i);
                    left(i);
                } else if (temp_arr[i] == 1) {
                    // 위 , 아래 , 오른쪽 감시
                    up(i);
                    down(i);
                    right(i);
                } else if (temp_arr[i] == 2) {
                    // 아래 , 오른쪽 , 왼쪽 감시
                    down(i);
                    right(i);
                    left(i);
                } else if (temp_arr[i] == 3) {
                    // 아래 , 왼쪽 , 위 감시
                    down(i);
                    left(i);
                    up(i);
                }
            } else if (cctv_arr[i].number == 5) {
                // 모든경우 사방 감시
                up(i);
                right(i);
                down(i);
                left(i);
            }
        }
        // 빈곳 카운트
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < M; k++) {
                if (map_clone[j][k] == 0) {
                    empty_cnt++;
                }
            }
        }
    } // end of solve
 
    private static void down(int i) {
        int cctv_r = cctv_arr[i].r;
        int cctv_c = cctv_arr[i].c;
        while (true) {
            cctv_r++;
            // 범위 넘거가거나 , 벽을 만나면 종료
            if (cctv_r >= N || map_clone[cctv_r][cctv_c] == 6)
                break;
            // 빈곳은 임의의 숫자 8로 마킹
            else if (map_clone[cctv_r][cctv_c] == 0)
                map_clone[cctv_r][cctv_c] = 8;
        }
    }
 
    private static void left(int i) {
        int cctv_r = cctv_arr[i].r;
        int cctv_c = cctv_arr[i].c;
        while (true) {
            cctv_c--;
            if (cctv_c < 0 || map_clone[cctv_r][cctv_c] == 6)
                break;
            else if (map_clone[cctv_r][cctv_c] == 0)
                map_clone[cctv_r][cctv_c] = 8;
        }
    }
 
    private static void right(int i) {
        int cctv_r = cctv_arr[i].r;
        int cctv_c = cctv_arr[i].c;
        while (true) {
            cctv_c++;
            if (cctv_c >= M || map_clone[cctv_r][cctv_c] == 6)
                break;
            else if (map_clone[cctv_r][cctv_c] == 0)
                map_clone[cctv_r][cctv_c] = 8;
        }
    }
 
    private static void up(int i) {
        int cctv_r = cctv_arr[i].r;
        int cctv_c = cctv_arr[i].c;
        while (true) {
            cctv_r--;
            if (cctv_r < 0 || map_clone[cctv_r][cctv_c] == 6)
                break;
            else if (map_clone[cctv_r][cctv_c] == 0)
                map_clone[cctv_r][cctv_c] = 8;
        }
    }
 
} // end of class

1. 입력시 빈곳의 개수 카운트하고

2. map_clone 맵핑하면서 따로 카운트해준뒤

3. map_clone에서 0인 곳 개수를 다시 카운트 할 필요없이 1 - 2 해주면 됨

이러면 의미있는지는 모르겠지만 150ms 단축