[JAVA] 백준 15683번 : 감시(삼성 SW 역량 테스트 기출 문제)

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

15683번: 감시

 

문제

DFS + 구현(Simultation) 문제이다.

해결 방안

CCTV 클래스를 만들어서 각 CCTV의 y(row), x(col), kinds(cctv 종류), dir[](해당 cctv가 가진 방향) 정보를 가지고 있도록 하였다.

1. Main에서 사무실 공간 값(map[i][j])을 입력 받을 때 cctv 값(1~5)가 포함되면 List<CCTV> cctvs에 넣어주었다.

2. cctvs 갯수(List 사이즈)만큼 DFS 탐색을 한다. 이때 DFS 탐색을 하는 목적은 List에 있는 CCTV들의 모든 방향을 설정해주기 위함이다.
이때 1,3,4 CCTV 같은 경우 4방향이 나올 수 있으므로 4가지 경우(90도씩 회전한 경우)를 DFS탐색을 해주고 2 CCTV 같은경우 2가지(상하, 좌우)의 경우를 DFS 탐색, 5 CCTV 같은 경우 1가지 경우를 DFS 탐색해준다.

3. CCTV 갯수만큼 DFS 탐색이 도달(기저사례)하게 되면 각 CCTV들이 감시하는 방향으로 copyMap을 재설정해준다. (문제의 예시에서는 #을 이용하였으나 여기서는 7값으로 해주었다.)

4. 그 후 copyMap에서 사각지대(0인 값) 인 부분을 세서 최소인 경우를 구해준다. 

 

코드

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

// 감시
// NxM 직사각형 사무실
// 총 k개의 cctv
// cctv 종류 5개 
// cctv는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있음
// 사무실에 벽이 있는데 cctv는 벽을 통과할 수 없다.
// cctv가 감시할 수 없는 영역은 사각지대
// cctv는 회전 시킬 수 있음(회전은 항상 90도 방향)
// 0은 빈칸 6은 벽 1~5는 cctv 번호

// 사각 지대의 최소 크기 출력
public class Main {
	
	static class CCTV{
		int y; // 세로
		int x; // 가로
		
		int kinds; // cctv 종류 (1~5)
		int[] dir; // 방향 (0~3)
		
		CCTV(int y, int x, int kinds){
			this.y = y;
			this.x = x;
			this.kinds = kinds;
			
			if(kinds==1) {
				this.dir = new int[1];
				dir[0] = 0;
			}
			else if(kinds==2) {
				this.dir = new int[2];
				dir[0] = 0;
				dir[1] = 2;
			}
			else if(kinds==3) {
				this.dir = new int[2];
				dir[0] = 0;
				dir[1] = 3;
			}
			else if(kinds==4) {
				this.dir = new int[3];
				dir[0] = 0;
				dir[1] = 2;
				dir[2] = 3;
			}
			else if(kinds==5) {
				this.dir = new int[4];
				dir[0] = 0;
				dir[1] = 1;
				dir[2] = 2;
				dir[3] = 3;
			}
		}
	}
	static int N; // 세로 (1~8)
	static int M; // 가로 (1~8)
	static int[][] map; // 사무실
	static int k; // cctv 갯수
	
	static List<CCTV> cctvs = new ArrayList<>();
	// 방향은 동 남 서 북
	static int[] dy = {0, 1, 0, -1}; // 세로
	static int[] dx = {1, 0, -1, 0}; // 가로
	
	static int result = Integer.MAX_VALUE; // 사각 지대의 최소 크기
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str;
		str = br.readLine();
		
		N = Integer.parseInt(str.split(" ")[0]);
		M = Integer.parseInt(str.split(" ")[1]);
		
		map = new int[N][M];
		
		StringTokenizer st;
		for(int i=0; i<N; i++) {
			str = br.readLine();
			st = new StringTokenizer(str, " ");
			for(int j=0; j<M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				
				// cctv 위치, 종류 List에 삽입
				if(map[i][j] >= 1 && map[i][j] <=5) {
					cctvs.add(new CCTV(i, j, map[i][j]));
				}
			}
		}
		k = cctvs.size();
		// ======= 입력 끝 ========
		dfs(0);
		
		System.out.println(result);
	}
	
	// y,x가 지도 범위 벗어나는지 확인
	static boolean isMapRange(int y, int x) {
		boolean flag = true;
		
		if(y<0 || y>=N || x<0|| x>=M)
			return false;
		
		return flag;
	}
	
	// copyMap에서 cctv가 감시중인 곳을 7로 바꿔줌
	static int[][] setCCTV(int[][] map){
		
		CCTV cctv;
		int cy, cx; // 세로, 가로
		int ny, nx;
		for(int i=0; i<cctvs.size(); i++) {
			cctv = cctvs.get(i);
			
			cy = cctv.y;
			cx = cctv.x;
			
			// i번째 cctv의 방향들로 감시하는 구역 값(7)로 바꿔줌
			int dir;
			for(int j=0; j<cctv.dir.length; j++) {
				dir = cctv.dir[j];// 해당 방향
				
				ny = cy;
				nx = cx;
				// j번째 방향을 7로 바꿔줌
				while(true) {
					ny += dy[dir];
					nx += dx[dir];
					
					// ny, nx 범위 확인(사무실내인지)
					if(isMapRange(ny, nx)) {
						// 빈 공간이면 감시 공간으로 바꿔줌
						if(map[ny][nx] == 0)
							map[ny][nx] = 7;
						// 벽에 도달하면 멈춤
						else if(map[ny][nx] == 6)
							break;
					}
					// 사무실 범위 벗어나면 멈춤
					else {
						break;
					}
					
				}
			}
		}
		
		return map;
	}
	
	// CCTV들 방향설정 및 감시하고 있는 영역을 구하는 함수
	static void dfs(int depth) {
		
		if(depth >= k) {
			
			// copyMap 복사
			int[][] copyMap = new int[N][M];
			for(int i=0; i<N; i++) {
				for(int j=0; j<M; j++) {
					copyMap[i][j] = map[i][j];
				}
			}
			
			// 정해진 방향으로 copyMap 재설정(cctv 감시중인 곳 #대신 7로)
			copyMap = setCCTV(copyMap);
			
			// 사각지대 갯수 구하기(0인 곳)
			int sum = 0;
			for(int i=0; i<N; i++) {
				for(int j=0; j<M; j++) {
					//System.out.print(copyMap[i][j]);
					if(copyMap[i][j] == 0)
						sum++;
				}
				//System.out.println();
			}
			//System.out.println();
			// 최소 사각지대 갯수 구하기
			result = Math.min(result, sum);
		}
		else {
			
			// 각 cctv 방향 설정
			CCTV cctv;
			cctv = cctvs.get(depth);
			
			int[] temp = cctv.dir.clone();
			// 1,3,4번 cctv인 경우 4방향
			if(cctv.kinds==1 || cctv.kinds==3 || cctv.kinds==4) {
				for(int j=0; j<4; j++) {
					
					for(int k=0; k<cctv.dir.length; k++) {
						cctv.dir[k] += j;
						cctv.dir[k] = cctv.dir[k] % 4;
					}
					dfs(depth+1);
					// dir 원래대로 돌려주기
					cctv.dir = temp.clone();
				}
			}
			// 2번 cctv인 경우 2방향 가능 (상하, 좌우)
			else if(cctv.kinds==2) {
				for(int j=0; j<2; j++) {
					for(int k=0; k<cctv.dir.length; k++) {
						cctv.dir[k] += j;
						cctv.dir[k] = cctv.dir[k] % 4;
					}
					dfs(depth+1);
					// dir 원래대로 돌려주기
					cctv.dir = temp.clone();
				}
			}
			// 5번 cctv인 경우 1방향
			else if(cctv.kinds==5) {
				dfs(depth+1);
			}
			
		}
		
	}

}