[백준/Java] 15683번 : 감시

[문제]

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.

1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.

CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.

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

지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호이다. 위의 예시에서 1번의 방향에 따라 감시할 수 있는 영역을 '#'로 나타내면 아래와 같다.

CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 칸을 감시할 수 없다.

위의 예시에서 감시할 수 있는 방향을 알아보면 아래와 같다.

CCTV는 CCTV를 통과할 수 있다. 아래 예시를 보자.

위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.

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

[조건]

• 시간 제한 : 1초
• 메모리 제한 : 512MB

[입력]

첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다. 

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

[출력]

첫째 줄에 사각 지대의 최소 크기를 출력한다.

[문제 풀이]

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

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static int N, M, P, cnt, count;
    static int[] dr, dc;
    static int[][] arr, check;
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][M];
        P = 1;
        cnt = N*M;
        ArrayList<int[]> list = new ArrayList<>();
        for (int r = 0; r < N; r++) {
            st = new StringTokenizer(br.readLine());
            for (int c = 0; c < M; c++) {
                arr[r][c] = Integer.parseInt(st.nextToken());
                if (0 < arr[r][c] && arr[r][c] < 6) {
                    list.add(new int[] { arr[r][c], r, c });
                    P*=4;
                    cnt--;
                }
                if(arr[r][c]==6) cnt--;
            }
        }
        
        dr = new int[] { -1, 0, 1, 0 };
        dc = new int[] { 0, -1, 0, 1 };
        
        int min = Integer.MAX_VALUE;
        for(int p=0; p<P; p++) {
        	check = new int[N][M];
            for (int i = 0; i < N; i++) {
                check[i] = Arrays.copyOf(arr[i], arr[i].length);
            }
        	count = cnt;
        	int order = p;
            for(int i=0; i<list.size(); i++) {
                int[] now = list.get(i);
                makeIDX(now[0], now[1], now[2], order%4);
                order/=4;
            }
            min = Math.min(count, min);
        }

        System.out.println(min);
    }    

    static public void makeIDX(int n, int r, int c, int d) {
    	int[] idx;
        if (n == 1) {
        	idx = new int[]{d};
        } else if (n == 2) {
        	idx = new int[] {d, (d+2)%4};
        } else if (n == 3) {
        	idx = new int[] {d, (d+1)%4};
        } else if (n == 4) {
        	idx = new int[] {d, (d+1)%4, (d+2)%4};
        } else {
        	idx = new int[] {0, 1, 2, 3};
        }
        delta(r, c, idx);
    }
    
    static public void delta(int r, int c, int[] idx) {
    	for(int i=0; i<idx.length; i++) {
    		int nr = r + dr[idx[i]];
    		int nc = c + dc[idx[i]];
    		while (nr >= 0 && nr < N && nc >= 0 && nc < M && check[nr][nc] != 6) {
    			if (check[nr][nc] == 0) {
    				check[nr][nc] = 7;
    				count--;
    			}
    			nr += dr[idx[i]];
    			nc += dc[idx[i]];
    		}
    	}
    }
}

 

[소감]

• 개인적으로 정말 정말 힘들게 푼 문제
• 경우의 수를 구하는 방법은 바킹독 강의 참고함

 

출처 : 백준 https://www.acmicpc.net/problem/15683