[백준] code.plus(브루트 포스 Part 1,JAVA)15683번, 감시

문제 링크

15683번: 감시

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감

www.acmicpc.net

주의사항

JAVA를 사용하여 프로그램을 사용하였습니다.
백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

문제 설명

접근 방법

이 문제에 핵심은

1. 5가지 종류의 CCTV는 90도로 회전할 수 있습니다.

2. CCTV를 구역을 감시하는 모든 경우 중 가장 사각지대 최소 크기를 결과로 출력합니다.

3. 사각 지대는 CCTV가 감시되지 않는 구역입니다.

4. CCTV는 감시할 때 벽에만 막힙니다.

알고리즘 진행 순서.

1. 입력되는 정보들을 저장합니다.

2. CCTV가 감시하는 모든 경우를 구해서 사각지대 최소 크기를 구합니다.

3. 사각지대 최소 크기를 결과로 출력합니다.

CCTV 감시

5번 CCTV

상하좌우 모두 탐색하기 때문에 하나의 경우 밖에 존재하지 않는다.

4번 CCTV

3가지 방향으로 탐색하기 때문에 4가지 경우가 존재한다.

{(←,↑,→), (↑,→,↓),(→,↓,←),(↓,←↑)}

※만약 4번 CCTV가 외곽에 있으면 인접한 외곽 칸 방향을 모두 탐색한다.

3번 CCTV

직각으로 탐색하기 때문에 4가지 경우가 존재한다.

{(↑,→), (→,↓),(↓,←),(←↑)}

※만약 4번 CCTV가 꼭지점에 있으면 인접한 외곽 칸 방향을 모두 탐색한다.

2번 CCTV

수평으로 탐색하기 때문에 2가지 경우가 존재한다.

{(←,→), (↑,↓)}

1번 CCTV

1가지 방향으로 탐색하기 때문에 4가지 경우가 존재한다.

{↑ , ↓, ←, →}

※저는 CCTV 감시를 진행할 때 번호가 높은 것부터 시작하였습니다.

예제입력 2.

1. 입력되는 정보들을 저장합니다.

N = 6, M = 6

0	0	0
2	0	0
0	6	0
6	2	0
0	0	0
0	0	5

2. CCTV가 감시하는 모든 경우를 구해서 사각지대 최소 크기를 구합니다.

CCTV 5번 탐색 시작

0	0	0
2	0	0
0	6	0
6	2	0
0	0	0
0	0	5

CCTV 2번(1,1) 탐색 시작

(←,→)

0	0	0
2	0	0
0	6	0
6	2	0
0	0	0
0	0	5

CCTV 2번(3, 4) 탐색

(←,→)

0	0	0
2	0	0
0	6	0
6	2	0
0	0	0
0	0	5

모든 CCTV 탐색 완료 ! : 사각지대 개수 = 15

CCTV 2번(3, 4) 탐색

(↑,↓)

0	0	0
2	0	0
0	6	0
6	2	0
0	0	0
0	0	5

모든 CCTV 탐색 완료 ! : 사각지대 개수 = 16

CCTV 2번(1,1) 탐색 시작

(↑,↓)

0	0	0
2	0	0
0	6	0
6	2	0
0	0	0
0	0	5

CCTV 2번(3, 4) 탐색

(←,→)

0	0	0
2	0	0
0	6	0
6	2	0
0	0	0
0	0	5

모든 CCTV 탐색 완료 ! : 사각지대 개수 = 17

CCTV 2번(3, 4) 탐색

(↑,↓)

0	0	0
2	0	0
0	6	0
6	2	0
0	0	0
0	0	5

모든 CCTV 탐색 완료 ! : 사각지대 개수 = 18

3. 사각지대 최소 크기를 결과로 출력합니다.

최소 크기 15를 결과로 출력합니다.

BufferedReader를 사용하여 입력 값을 받았습니다.
StringTokenizer를 이용하여 입력값을 띄어쓰기 기준으로 나누었습니다.
Collections.sort()를 이용하여 CCTV번호 기준 내림차순 정렬하였습니다.
search을 실행하여 CCTV 감시하는 모든 경우에 사각지대 최소 크기를 BufferedWriter 저장하였습니다.
BufferedWriter에 저장된 결과값을 출력하였습니다.

search함수는 CCTV를 감시하는 모든 경우를 탐색하여 사각지대 최소 값을 구합니다.
cctv5, cctv4, cctv2And3함수는 각 CCTV번호에 따른 감시를 진행합니다.
cctvSearch함수는 주어진 방향으로 CCTV 감시를 진행합니다.
rollBack함수는 복사한 원래 공간 정보로 되돌리는 것을 진행합니다.
inSpace함수는 이동하려는 칸이 공간에 존재하는지 확인합니다.
cctvCheck함수는 공간에 사각지대가 몇 개있는지 구하는 함수입니다.

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    //CCTV 관련 정보 클래스
    static class cctv implements Comparable<cctv>{
        int x, y, index;
        public cctv(int x, int y, int index) {
            this.x = x;
            this.y = y;
            this.index = index;
        }
        //CCTV 번호 기준 내림차순 정렬
        @Override
        public int compareTo(cctv o) {
            return o.index - this.index;
        }
    }
    static int[][] map;		//공간 정보 저장 배열
    static int N,M, answer = Integer.MAX_VALUE;
    static int[] dx = {0, 0, -1, 1};	//상하좌우 x변경값
    static int[] dy = {-1, 1, 0, 0};	//상하좌우 y변경값
    static ArrayList<cctv> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        //공간 정보 저장
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<M;j++){
                int num = Integer.parseInt(st.nextToken());
                if(num>0){
                    if(num<=5)
                        list.add(new cctv(j,i, num));
                    map[i][j] = num;
                }

            }
        }
        Collections.sort(list);	//CCTV 번호 기준 내림차순 정렬
        search(0);		//CCTV 감시하는 모든 경우 탐색 및 최소 크기 구하기
        bw.write(answer + "");		//최소크기 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    static void search(int depth ){
        if(depth==list.size()){		//모든 CCTV 감시 완료시
            cctvCheck();
            return;
        }
        cctv cur = list.get(depth);	//현재 CCTV
        if(cur.index==5){		//5번 CCTV일 때
            cctv5(cur);
            search(depth+1);
            return;
        }
        //현재 공간 상태 복사
        int[][] temp = new int[N][M];
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++)
                temp[i][j] = map[i][j];
        }
        //4번 CCTV일 때
        if(cur.index==4){
            //외곽에 있을 때
            if(cur.x==0 || cur.x==M-1 || cur.y == 0 || cur.y==N-1){
                for(int i=0;i<4;i++)
                    cctvSearch(cur.x, cur.y, i);
                search(depth+1);
            }else{
                cctv4(cur, 0,3,1);
                search(depth+1);
                rollback(temp);
                cctv4(cur, 3,1,2);
                search(depth+1);
                rollback(temp);
                cctv4(cur, 0,1,2);
                search(depth+1);
                rollback(temp);
                cctv4(cur, 2,0,3);
                search(depth+1);
                rollback(temp);
            }
        }else if(cur.index==3){		//3번 CCTV일 때
            //꼭지점에 있을 때
            if((cur.x==0&&cur.y==0)||(cur.x==0&&cur.y==N-1) ||(cur.x==M-1 && cur.y==0) || (cur.x==M-1 && cur.y==N-1)){
                for(int i=0;i<4;i++)
                    cctvSearch(cur.x, cur.y, i);
                search(depth+1);
            }else{
                cctv3And2(cur, 0, 3);
                search(depth+1);
                rollback(temp);
                cctv3And2(cur, 3, 1);
                search(depth+1);
                rollback(temp);
                cctv3And2(cur, 1, 2);
                search(depth+1);
                rollback(temp);
                cctv3And2(cur, 2, 0);
                search(depth+1);
                rollback(temp);
            }
        }else if(cur.index==2){	//2번 CCTV일 때
            cctv3And2(cur, 0, 1);
            search(depth+1);
            rollback(temp);
            cctv3And2(cur, 2, 3);
            search(depth+1);
            rollback(temp);
        }else if(cur.index==1){	//1번 CCTV일 때
            for(int i=0;i<4;i++){
                cctvSearch(cur.x, cur.y, i);
                search(depth+1);
                rollback(temp);
            }
        }
    }
    //CCTV5번이 감시를 진행하는 함수
    static void cctv5(cctv cur) {
        for (int i = 0; i < 4; i++)
            cctvSearch(cur.x, cur.y, i);
    }
    //CCTV 4번이 감시를 진행하는 함수
    static void cctv4(cctv cur, int d1, int d2, int d3){
        cctvSearch(cur.x, cur.y, d1);
        cctvSearch(cur.x, cur.y, d2);
        cctvSearch(cur.x, cur.y, d3);
    }
    //CCTV 2번, 3번이 감시를 진행하는 함수
    static void cctv3And2(cctv cur, int d1, int d2){
        cctvSearch(cur.x, cur.y, d1);
        cctvSearch(cur.x, cur.y, d2);
    }
    //CCTV 감시 이전으로 돌리는 함수
    static void rollback(int[][] temp){
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++)
                map[i][j] = temp[i][j];
        }
    }
    //CCTV 주어진 방향으로 탐색하는 함수
    static void cctvSearch(int x, int y, int direction){
        while(true){
            x += dx[direction];
            y += dy[direction];
            if(!inSpace(x,y) || map[y][x]==6)
                break;
            if(map[y][x]==0)
                map[y][x] = -1;
        }
    }
    //이동하려는 칸이 공간에 존재하는지 확인하는 함수
    static boolean inSpace(int x, int y){
        if(x >= 0 && y>=0 && x<M && y<N)
            return true;
        return false;
    }
    //사각지대 개수 구하는 함수
    static void cctvCheck(){
        int result = 0;
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(map[i][j]==0)
                    result++;
            }
        }
        answer = Math.min(answer, result);
    }
}

저작자표시

'백준' 카테고리의 다른 글

[백준] code.plus(브루트 포스 Part 1,JAVA)15686번, 치킨 배달 (0)	2022.08.27
[백준] code.plus(브루트 포스 Part 1,JAVA)17088번, 등차수열 변환 (0)	2022.08.26
[백준] code.plus(브루트 포스 Part 1,JAVA)16637번, 괄호 추가하기 (0)	2022.08.24
[백준] code.plus(브루트 포스 Part 1,JAVA)16943번, 숫자 재배치 (0)	2022.08.23
[백준] code.plus(브루트 포스 Part 1,JAVA)16938번, 캠프 준비 (0)	2022.08.22

찬형이의 공부방

[백준] code.plus(브루트 포스 Part 1,JAVA)15683번, 감시

문제 링크

주의사항

문제 설명

접근 방법

'백준' 카테고리의 다른 글

댓글

티스토리툴바

[백준] code.plus(브루트 포스 Part 1,JAVA)15683번, 감시

문제 링크

주의사항

문제 설명

접근 방법

'백준' 카테고리의 다른 글

관련글

댓글

티스토리툴바