백준 15683번 : 감시

 문제

www.acmicpc.net/problem/15683

15683번: 감시

15683 감시

 

 구현 방법

 cctv가 가질 수 있는 경우의 수를 다 계산하여 사각지대의 최소 크기를 구해줘야 합니다.

cctv의 좌표, 번호를 리스트에 저장하고 리스트의 크기만큼 방향을 가지는 순열을 구해줍니다.

선택된 방향으로 가능성을 다 확인 후 사각지대 개수를 카운트 하여 제일 최솟값을 출력해줍니다.

cctv5는 어느 방향 상관없이 인접한 곳을 다 확인하므로 반복을 피하기 위해 따로 저장해주어 감시를 해주었습니다.

 

 구현 코드

package baekjoon.gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ15683_감시 {
	static int R, C, size, MIN, cnt;
	static List<cctv> list, list5;
	static int[] numbers;
	static boolean[] isSelect;
	static int[][] office, temp, deltas= {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; // 상 좌 하 우
	static class cctv{
		int r, c, num;

		public cctv(int r, int c, int num) {
			super();
			this.r = r;
			this.c = c;
			this.num = num;
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		office = new int[R][C];
		list = new ArrayList<>();
		list5 = new ArrayList<>();
		for (int r=0;r<R;r++) {
			st = new StringTokenizer(br.readLine());
			for (int c=0;c<C;c++) {
				office[r][c] = Integer.parseInt(st.nextToken());
				if (office[r][c]==5) list5.add(new cctv(r, c, office[r][c])); // cctv5번일 때 
				else if (office[r][c]!=0 && office[r][c]!=6) list.add(new cctv(r, c, office[r][c])); // cctv 저장
			}
		}
		// 입력완료
		for (int i=0;i<list5.size();i++) { // cctv5번이면 미리 상하좌우 칠해줌
			cctv now = list5.get(i);
			for (int d=0;d<4;d++) set(now.r, now.c, d, office);
		}
		size = list.size();
		numbers = new int[size];
		isSelect = new boolean[4];
		MIN = Integer.MAX_VALUE;
		permutation(0); // 순열 구하기 ( 각 cctv에서 갈 방향 )
		System.out.println(MIN);
	}
	
	static void permutation(int pos) {
		if (pos==size) {
			temp = new int[R][C];
			for (int r=0;r<R;r++) { // 배열 복사
				for (int c=0;c<C;c++) {
					temp[r][c] = office[r][c];
				}
			}
			surve(); // 감시 확인
			
			MIN = Math.min(MIN, cnt);
			if (MIN==0) { // 사각지대가 없으면 바로 끝내주기
				System.out.println(0);
				System.exit(0);
			}
			return;
		}
		
		for (int i=0;i<4;i++) {
			numbers[pos] = i;
			isSelect[i] = true;
			permutation(pos+1);
			isSelect[i] = false;
		}
	}
	
	static void surve() {
		cnt = 0; 
		for (int i=0;i<size;i++) {
			cctv now = list.get(i);
			check(now.r, now.c, now.num, numbers[i]); // cctv 좌표와 번호, 갈 방향 넘겨줌
		}
		
		for (int i=0;i<R;i++) {
			for (int j=0;j<C;j++) {
				if (temp[i][j]==0) cnt++; // 사각지대 검사
			}
		}
	}
	
	static void check(int r, int c, int num, int d) {
		set(r, c, d, temp); // 공통으로 확인
		if (num==2) set(r, c, (d+2)%4, temp); // cctv가 2라면 반대방향도 확인
		else if (num==3) set(r, c, (d+1)%4, temp); // cctv가 3이라면 바로 옆도 확인
		else if (num==4) { // cctv가 4라면 3방향 확인
			set(r, c, (d+1)%4, temp);
			set(r, c, (d+2)%4, temp);
		}
	}
	
	static void set(int r, int c, int d, int[][] arr) {
		while(true) {
			int nr = r+deltas[d][0];
			int nc = c+deltas[d][1];
			if (isIn(nr, nc)) {
				if (arr[nr][nc]!=6) arr[nr][nc]=9; // 장애물이 없다면 9로 바꿔줌
				if (arr[nr][nc]==6) break; // 장애물 있다면 그만!
			} else break; // 범위 벗어난다면 그만!
			 
			r = nr; c = nc;
		}
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<R && nc>=0 && nc<C;
	}
}

 

정답!