[ 알고리즘 ] 코딩 - 백준 - 15683 - 감시.java

www.acmicpc.net/problem/15683

15683번: 감시

CCTV 번호 별 감시 영역

---

* 사용한 로직!

* 1. 순열로 CCTV별 감시 방향을 정해준다

* 1-1. 감시 방향을 정할 때 CCTV마다 규칙이 있으니 주의해서 설정!

* 2. 정해진 방향을 기준으로 감시 영역을 표시한다.

* 3. 남은 사각지대의 영역을 카운트 해준다.

* 처음에는 CCTV Type마다 따로 저장하기 위해 ArrayList 배열을 사용했다.

---

private static void selectCCTVdir(int idx, int type) {
		if(type == 5) { // 5번 타입은 방향지정이 필요 없다.
			// 정해진 순서를 가지고 BFS 수행
			int tmpMap[][] = new int[N][M];
			initMap(tmpMap);
			setRoute(tmpMap);
			int cnt = findZero(tmpMap);
			
			resMin = Math.min(cnt, resMin);
			return ;
		}
		if(idx == cctvList[type].size()) {
			selectCCTVdir(0, type+1);
			return ;
		}
		int dir = 4;
		if(type == 2) dir = 2; // 2번 CCTV는 우, 상만 있으면 된다.
		for(int i = idx; i < cctvList[type].size(); i++) {
			for(int d = 0; d < dir; d++) {
				// 시작 지점을 정해주자.
				cctvList[type].get(i).dir = d;
				selectCCTVdir(i+1, type);
			}
		}
	}

* dfs안에 return 문이 2개..! 왜 이렇게 생각했지?!!!

* 그런데 생각해보니 필요 없는 과정이라 간결하게 바꿨다!

---

* 아래가 전체 코드

public class BOJ_15683_감시 {
	private static class CCTV{ // 각 cctv의 정보를 담을 객체
		int y, x, dir, type;

		public CCTV(int y, int x, int dir, int type) {
			this.y = y;
			this.x = x;
			this.dir = dir;
			this.type = type;
		}
	}
	
	private static int N, M, resMin, map[][];
							// 우, 상, 좌, 하 -> 반시계방향으로 인덱스를 사용할것이다.
	private static int dx[] = {1, 0, -1, 0};
	private static int dy[] = {0, -1, 0, 1};
	private static List<CCTV> cctvList;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stt = new StringTokenizer(br.readLine(), " ");
		
		N = Integer.parseInt(stt.nextToken());
		M = Integer.parseInt(stt.nextToken());
		cctvList = new ArrayList<>();
		map = new int[N][M];
		
		for(int i = 0; i < N; i++) {
			stt = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < M; j++) {
				int in = Integer.parseInt(stt.nextToken());
				if(in != 0 && in < 6) { // CCTV인 경우만
                    // y, x, 방향, type
					cctvList.add(new CCTV(i, j, 0, in));
				}
				map[i][j] = in;
			}
		} // input end
		
		resMin = Integer.MAX_VALUE;
		// type별로 CCTV의 방향을 정하자.
		selectCCTVdir(0, cctvList.size());
		
		System.out.println(resMin);
	}
	
    /* 전체 CCTV의 방향을 정할 순열 DFS
     * idx : cctv 카운트
     * listsize : 전체 cctv 개수
     */
	private static void selectCCTVdir(int idx, int listsize) {
		if(idx == listsize) { // cctv 배치 완료
			int tmpMap[][] = new int[N][M]; // 맵 복사해서 쓸거야
			initMap(tmpMap); // 초기화
			setRoute(tmpMap); // 감시 영역 설정
			int cnt = findZero(tmpMap); // 0 카운트
			
			resMin = Math.min(cnt, resMin); // 최솟값 갱신
			return ;
		}
		int dir = 4; // 2번 카메라를 제와한 나머지는 0, 1, 2, 3 방향 모두 이용
		for(int i = idx; i < listsize; i++) {
			CCTV cctv = cctvList.get(i);
			if(cctv.type == 5) { // 5번 카메라는 방향 설정 필요 x
				selectCCTVdir(i+1, listsize);
				continue;
			}
			if(cctv.type == 2) dir = 2; // 2번 CCTV는 우, 상만 있으면 된다.
			for(int d = 0; d < dir; d++) {
				// 시작 방향을 정해주자.
				cctv.dir = d;
				selectCCTVdir(i+1, listsize);
			}
		}
	}
	
    /* 0의 갯수를 카운팅 */
	private static int findZero(int[][] tmpMap) {
		int res = 0;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(tmpMap[i][j] == 0) res++;
			}
		}
		return res;
	}

	/** 맵 복사 */
	private static void initMap(int[][] tmpMap) {
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				tmpMap[i][j] = map[i][j];
			}
		}
	}

	/** CCTV의 방향대로 -1을 채워주자 */
	private static void setRoute(int[][] tmpMap) {
		// 모든 CCTV의 정보를 얻어오자
		for(int j = 0; j < cctvList.size(); j++) {
			CCTV curCCTV = cctvList.get(j);
			int next_y = curCCTV.y;
			int next_x = curCCTV.x;
			int dir = curCCTV.dir;
			int type = curCCTV.type;
			for(int d = 0; d < 4; d++) {
				if(type == 1) { // 1번 카메라는 한 방향
					if(d != 0) continue;
				}
				else if(type == 2) {  // 2번 카메라 선택한 방향 + 180도 뒤 방향
					if(d == 1 || d == 3) continue;
				}
				else if(type == 3) { // 3번 카메라 선택 방향 + 90도 {
					if(d == 2 || d == 3) continue;
				}
				else if(type == 4) { // 4번 카메라 선택방향 + 90도 + 180도
					if(d == 3) continue;
				} // 5번 카메라는 4방향
				next_y += dy[(dir+d)%4]; // 나머지 연산으로 인덱스 계산
				next_x += dx[(dir+d)%4];
				
                // 범위를 벗어나거나 벽을 만난 경우에는 원래 자리에서 다른 방향 계산
				if(rangeCheck(next_y, next_x) || tmpMap[next_y][next_x] == 6 ) {
					next_y = curCCTV.y;
					next_x = curCCTV.x;
					continue;
				}
                
                // -1 채워주자!
				tmpMap[next_y][next_x] = -1;
				d--; // bfs가 아니라 한 방향으로 나아가야하기 때문에 d--를 해주자
			}
		}
	}
	
	/** 범위 체크 */
	private static boolean rangeCheck(int y, int x) {
		return y < 0 || y >= N || x < 0 || x >= M;
	}
}