[BJ]BJ_G5_15683_감시

BJ_G5_15683_감시

 

 

문제링크

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

15683번: 감시

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

BJ_G5_15683_감시 (naver.com)

BJ_G5_15683_감시

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package algo_class;

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

/**
 * @author 은서파
 * @since 2021. 8. 18.
 * @see https://www.acmicpc.net/problem/15683
 * @perf 14600	124
 * @category #완탐, #시뮬레이션 
 * @고려사항
 * 5번 카메라는 DFS로 돌릴 필요 없이 미리 처리해 두어도 괜찮지만 1번 도는거라 그런지 효과는 거의 없다.
 * @입력사항
 * @출력사항
 */

public class BJ_G5_15683_감시 {

	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;
	
	// CCTV 타입 별로 바라볼 수 있는 방향의 쌍들을 미리 정해두자.
	static int [][][] watchDirs = {
			{}, // 0번 타입
			{{0}, {1},{2},{3}}, // 1번 타입
			{{0, 1},{2,3}}, // 2번타입
			{{0, 2},{2, 1},{1, 3},{3, 0}},// 3번 타입
			{{0, 1, 2},{0, 1, 3},{0, 2, 3},{1, 2, 3}}, // 4번 타입 
			{{0, 1, 2, 3}}// 5번 타입 
			
	};
	
	static int [][] deltas = {{-1, 0},{1, 0},{0, 1},{0, -1}};

	static int R, C, MIN;
	static int [][] map;
	// 관리할 CCTV 목록 
	static List<CCTV> cctvs;
	// 초기 상태에서 관리해야 할 지점의 개수
	static int whiteArea = 0;
	
	public static void main(String[] args) throws IOException {
		input = new BufferedReader(new StringReader(src));
		
		tokens = new StringTokenizer(input.readLine());
		R = Integer.parseInt(tokens.nextToken());
		C = Integer.parseInt(tokens.nextToken());
		
		map = new int [R][C];
		cctvs  =new ArrayList<>();
		for(int r=0; r<R; r++) {
			tokens = new StringTokenizer(input.readLine());
			for(int c=0; c<C; c++) {
				map[r][c] = Integer.parseInt(tokens.nextToken());
				//CCTV 발견!!
				if(map[r][c] >0 && map[r][c]<6) {
					cctvs.add(new CCTV(r, c, map[r][c]));
				}else if(map[r][c]==0) {
					whiteArea++;
				}
			}
		}
		// System.out.println("white area: "+whiteArea+", cctv : "+cctvs);
		// 입력 완료
		MIN = Integer.MAX_VALUE;
		dfs(0, 0);
		System.out.println(MIN);
	}
	
	static void dfs(int cctvIdx, int clearSpot) {
		// 기저조건
		if(cctvIdx == cctvs.size()) {
			// 그럼 현 시점에서의 최소 사각은? 
			MIN = Math.min(MIN, whiteArea - clearSpot);
			return ;
		}
		
		
		// CCTV를 한대 가져온다. --> 그녀석이 볼 수 있는 방향으로 회전시켜본다.!!
		CCTV cctv = cctvs.get(cctvIdx);
		for(int d=0; d<watchDirs[cctv.t].length; d++) {
			// 이때의 방향은?
			int [] dirs = watchDirs[cctv.t][d];
			// dirs 방향으로 찾아보기. --> 맵 오염 
			int scaned = scan(cctv, dirs, -1);
			
			dfs(cctvIdx+1, clearSpot + scaned);
			
			// dirs 방향에 대해서 맵 원복..
			scan(cctv, dirs, 1);
		}
	}
	
	/**
	 * 
	 * @param cctv - 사용할 CCTV
	 * @param dirs - 그 CCTV가 보는 방향 정
	 * @param flag - 오염(-1), 원복(+1) 
	 * @return 현재의 CCTV가 볼 수 있는 방향에서 처리할 수 있는 영역의 개수 
	 */
	static int scan(CCTV cctv, int [] dirs, int flag) {
		int cnt = 0;
		for(int d=0; d<dirs.length; d++) {
			for(int i=1; ; i++) {
				int nr = cctv.r + deltas[dirs[d]][0]*i;
				int nc = cctv.c + deltas[dirs[d]][1]*i;
				
				if( !isIn(nr, nc) || map[nr][nc]==6) {
					break;
				}
				// 다른 CCTV - 생략하고 다음꺼 체크하러 가기. 
				if(map[nr][nc]>0) {
					continue;
				}
				// 사각해소지역 증가.
				if(map[nr][nc]==0) {
					cnt++;
				}
				// flag에 따라서 오염/원복.
				map[nr][nc] +=flag;
			}
		}
		return cnt;
	}
	
	static boolean isIn(int r, int c) {
		return 0<=r && r<R && 0<=c && c<C;
	}
	
	
	
	static class CCTV{
		int r, c, t; // row, col, type

		public CCTV(int r, int c, int t) {
			super();
			this.r = r;
			this.c = c;
			this.t = t;
		}

		@Override
		public String toString() {
			return "CCTV [r=" + r + ", c=" + c + ", t=" + t + "]";
		}
		
		
	}

	private static String src = "4 6\r\n"	+
								"0 0 0 0 0 0\r\n" +
								"0 0 0 0 0 0\r\n" +
								"0 0 1 0 6 0\r\n" +
								"0 0 0 0 0 0";

}