[백준 온라인 저지(BOJ), 브루트 포스] 삼성 코딩 테스트 문제 :: 15683번 감시 자바 풀이

이 문제는 난이도가 조금 있다고 생각해요

처음에 어떻게 풀어야 될까 고민을 좀 많이 했어요

코드만 본다면 어려워 보이진 않지만 그동안 풀었던 브루트 포스 문제랑은 조금 달랐어요

cctv마다 방향을 4가지 바꿔서 돌려줘야 했기 떄문이었어요

 

문제는 아래 사이트에서 풀어보실 수 있어요

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

15683번: 감시

 

저는 CCTV 클래스를 만들어서 입력받을 때 cctv의 위치와 cctv번호를 저장했어요

그리고 dfs방식으로 문제를 풀었어요. 방향을 한 번씩 바꿔가면서요

예를들어 cctv가 3개가 있다면 1,2번 cctv는 그대로 두고 3번 cctv를 4가지 방향으로 모두 돌려봐요

그 다음은 2번 cctv를 90도 방향으로 한 번 돌리고 3번 cctv를 다시 4가지 방향으로 모두 돌려요

이러한 식으로 모든 경우를 계산했어요

 

이떄 1-4번 cctv마다 감시할 수 있는 영역이 다르기 때문에

함수를 모두 따로 만들어서 계산해주었어요

그렇게 map을 바꿔주고 사각 지대의 크기를 저장해주었어요

그렇게 모든 경우의 사각 지대의 크기를 저장해두고 collections를 이용해서 최소값을 출력해주었어요

 

아래에 코드 올려놓은 깃 허브 주소있으니 참고하세요!!

https://github.com/wlgh325/BOJ_answer/tree/master/15683(Surveillance)

wlgh325/BOJ_answer

 

<백준 온라인 저지 15683번 감시 자바 풀이>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

class CCTV{
	int x;
	int y;
	int num;
	int dir;
	
	CCTV(int x, int y, int num){
		this.x = x;
		this.y = y;
		this.num = num;
	}

	CCTV(CCTV cctv){
		this.x = cctv.x;
		this.y = cctv.y;
		this.num = cctv.num;
		this.dir = cctv.dir;
	}
}

class Main {
	// 사각지대 : CCTV가 감시할 수 없는 영역
	// cctv 회전 가능 (90도)
	
	// 사각지대 최소 값 구하기 ( 0의 개수가 최소 )
	
	
	/*	
		0: 빈칸
		6: 벽
		1~5: cctv
	*/
	static int[][] map;	// 사무실
	static ArrayList<Integer> sumList;
	static ArrayList<CCTV> arrList;
	static int height;
	static int width;
	static boolean[] visited;
	static ArrayList<CCTV> comb;
	static int cctvNum;

	// 모든 경우 따져서 0의 개수가 최소가 되는 경우 구하기
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String input = br.readLine();
		String[] temp = input.split(" ");
		height = Integer.parseInt(temp[0]);
		width = Integer.parseInt(temp[1]);

		map = new int[height][width];
		arrList = new ArrayList<>();
		
		sumList = new ArrayList<>();
		comb = new ArrayList<>();

		for(int i=0; i<height; i++){
			String input2 = br.readLine();
			String[] temp2 = input2.split(" ");
			for(int j=0; j<width; j++){
				int temp_num = Integer.parseInt(temp2[j]);
				if(temp_num !=0 && temp_num != 6){
					CCTV cctv = new CCTV(i,j,temp_num);
					arrList.add(cctv);
				}
				map[i][j] = temp_num;
			}
		}

		cctvNum = arrList.size();
		visited = new boolean[cctvNum];

		// dir을 하나씩 바꿔가면서 해야함
		dfs(0);

		System.out.println(Collections.min(sumList));
	}

	static void dfs(int r){
		if(r==cctvNum){
			start();
			return;
		}
		for(int i=0; i<4; i++){
			arrList.get(r).dir = i;
			dfs(r+1);
		}
		
	}

	static void start(){
		ArrayList<CCTV> copyList = new ArrayList<>();;
		int[][] tempMap;

		for(int j=0; j< arrList.size(); j++){
			copyList.add(new CCTV(arrList.get(j)));
		}
		
		tempMap = deepCopy(map);
		for(int j=0; j<cctvNum; j++){
			surveillance(tempMap, copyList.get(j));
		}
		sumList.add(calCulate(tempMap));
	}
	
	static int[][] deepCopy(int[][] original2){
		if(original2 == null) return null;
		int[][] result = new int[original2.length][original2[0].length];
		 
		for(int i=0; i<original2.length; i++){
			System.arraycopy(original2[i], 0, result[i], 0, original2[0].length);
		}
		 
		return result;
	}

	static int calCulate(int[][] map){
		int sum=0;
		for(int i=0; i<height; i++){
			for(int j=0; j<width; j++){
				if(map[i][j] ==0)
					sum+=1;
			}
		}

		return sum;
	}

	static void surveillance(int[][] map, CCTV cctv){
		switch(cctv.num){
			case 1:
				surveillance1(map, cctv);
				break;
			case 2:
				surveillance2(map,cctv);
				break;
			case 3:
				surveillance3(map, cctv);
				break;
			case 4:
				surveillance4(map, cctv);
				break;
			case 5:
				surveillance5(map, cctv);
		}
	}

	// 0: 북
	// 1: 동
	// 2: 남
	// 3: 서
	static void surveillance1(int[][] map, CCTV cctv){
		switch(cctv.dir){
			case 0:
				surveillanceNorth(map, cctv);
				break;
			case 1:
				surveillanceEast(map, cctv);
				break;
			case 2:
				surveillanceSouth(map, cctv);
				break;
			case 3:
				surveillanceWest(map, cctv);

		}
	}

	// 0: 가로
	// 1: 세로
	static void surveillance2(int[][] map, CCTV cctv){
		switch(cctv.dir){
			case 0:
				surveillanceEast(map, cctv);
				surveillanceWest(map, cctv);
				break;
			case 1:
				surveillanceNorth(map, cctv);
				surveillanceSouth(map, cctv);
		}
	}

	// 0: 북, 동
	// 1: 동, 남
	// 2: 남, 서
	// 3: 서, 북
	static void surveillance3(int[][] map, CCTV cctv){
		switch(cctv.dir){
			case 0:
				surveillanceNorth(map, cctv);
				surveillanceEast(map, cctv);
				break;
			case 1:
				surveillanceEast(map, cctv);
				surveillanceSouth(map, cctv);
				break;
			case 2:
				surveillanceSouth(map,cctv);
				surveillanceWest(map, cctv);
				break;
			case 3:
				surveillanceWest(map,cctv);
				surveillanceNorth(map, cctv);
		}
	}

	// 0: 동, 서, 북
	// 1: 동, 남, 북
	// 2: 동, 서, 남
	// 3: 서, 남, 북
	static void surveillance4(int[][] map, CCTV cctv){
		switch(cctv.dir){
			case 0:
				surveillanceEast(map, cctv);
				surveillanceWest(map, cctv);
				surveillanceNorth(map, cctv);
				break;
			case 1:
				surveillanceEast(map, cctv);
				surveillanceSouth(map, cctv);
				surveillanceNorth(map, cctv);
				break;
			case 2:
				surveillanceEast(map, cctv);
				surveillanceWest(map, cctv);
				surveillanceSouth(map, cctv);
				break;
			case 3:
				surveillanceWest(map, cctv);
				surveillanceSouth(map, cctv);
				surveillanceNorth(map, cctv);

		}
	}

	static void surveillance5(int[][] map, CCTV cctv){
		surveillanceEast(map, cctv);
		surveillanceWest(map, cctv);
		surveillanceSouth(map, cctv);
		surveillanceNorth(map, cctv);
	}

	static boolean isWall(int i){
		if(i == 6)
			return true;
		return false;
	}

	static void surveillanceNorth(int[][] map, CCTV cctv){
		for(int i=1; cctv.x - i>=0; i++){
			if(isWall(map[cctv.x-i][cctv.y]))
				break;
			map[cctv.x-i][cctv.y] = 7;
		}
	}

	static void surveillanceEast(int[][] map, CCTV cctv){
		for(int i=1; cctv.y + i <width; i++){
			if(isWall(map[cctv.x][cctv.y +i])){
				break;
			}
			map[cctv.x][cctv.y + i] = 7;
		}
	}

	static void surveillanceSouth(int[][] map, CCTV cctv){
		for(int i=1; cctv.x +i <height; i++){
			if(isWall(map[cctv.x +i][cctv.y]))
				break;
			map[cctv.x+i][cctv.y] = 7;
		}
	}

	static void surveillanceWest(int[][] map,CCTV cctv){
		for(int i=1; cctv.y - i>=0; i++){
			if(isWall(map[cctv.x][cctv.y -i]))
				break;
			map[cctv.x][cctv.y - i] = 7;
		}
	}
}