알고리즘 문제풀이/BOJ
[백준 온라인 저지(BOJ), 브루트 포스] 삼성 코딩 테스트 문제 :: 15683번 감시 자바 풀이
- -
이 문제는 난이도가 조금 있다고 생각해요
처음에 어떻게 풀어야 될까 고민을 좀 많이 했어요
코드만 본다면 어려워 보이진 않지만 그동안 풀었던 브루트 포스 문제랑은 조금 달랐어요
cctv마다 방향을 4가지 바꿔서 돌려줘야 했기 떄문이었어요
문제는 아래 사이트에서 풀어보실 수 있어요
https://www.acmicpc.net/problem/15683
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할
www.acmicpc.net
저는 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
Contribute to wlgh325/BOJ_answer development by creating an account on GitHub.
github.com
<백준 온라인 저지 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;
}
}
}
Contents
소중한 공감 감사합니다