백준 알고리즘 - 감시

CCTV의 종류는 총 5개지만
종류마다 방향의 개수가 정해져있지만,
모두 4방향의 경우가 있다고 가정하고 문제를 접근했다.
물론 5번카메라 같은 경우는 방향이 1가지 이기 때문에 이 요소를 고려하고 짠다면,
불필요한 연산을 하지 않아도 된다.

CCTV의 개수는 8개를 넘지 않는다고 하였다.
이 말은 4의 8제곱의 경우의 수를 넘지 않는다.
DFS를 통해 탐색 후 CCTV가 감시하는 부분을 7로 채운 후
마지막의 0의 개수를 세어서 HashSet에 다가 넣어주었다.
그리고 다시 7로 채운 부분을 0으로 돌려주었다.
이 과정을 모든 경우의 수 만큼 반복했다.
모든 경우의 수를 검사하고 난 후 최소값을 출력해 주도록 짰다.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;

public class Main {
    private static class CCTV{
        int x;
        int y;
        int type;
        boolean visited[];

        public CCTV(int x, int y, int type) {
            this.x = x;
            this.y = y;
            this.type = type;
            this.visited = new boolean[4];
        }
    }

    private static int[] resultDirections;
    private static int[][] room;
    private static int directions = 4;
    private static int cctvCnt = 0;//cctv 개수
    private static ArrayList<CCTV> allCCTV = new ArrayList<>();

    private static HashSet<Integer> resultZero = new HashSet<>();

    private static int height;
    private static int width;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        height = sc.nextInt();
        width = sc.nextInt();

        room = new int[height][width];

        for(int i=0; i<height; i++) {
            for(int j=0; j<width; j++) {
                room[i][j] = sc.nextInt();
                if(room[i][j] == 0 || room[i][j] == 6)
                    continue;
                allCCTV.add(new CCTV(i, j, room[i][j]));
            }
        }


        cctvCnt = allCCTV.size();
        resultDirections = new int[cctvCnt];
        DFS();
        System.out.println(minZeroCnt(resultZero));
    }

    private static void DFS(){
        if (cctvCnt > 0) {
            for (int i = 0; i < directions; i++) {
                CCTV cctv = allCCTV.get(0);
                cctv.visited[i] = true;
                DFS_recursion(0, i);
            }
        } else {
            int zeroCnt = printRoomAndCountZero(room);
            resultZero.add(zeroCnt);
        }
    }

    private static void DFS_recursion(int depth, int direction){
        resultDirections[depth] = direction;
        if (depth == cctvCnt-1) {
            for (int i = 0; i < resultDirections.length; i++){
                CCTV cctv = allCCTV.get(i);
                mark7(cctv.type, resultDirections[i], cctv.x, cctv.y);
            }
            int zeroCnt = printRoomAndCountZero(room);
            resultZero.add(zeroCnt);
            getBack7to0(room);
        } else {
            for (int i = 0; i < directions; i++){
                CCTV cctv = allCCTV.get(depth + 1);
                if (cctv.visited[i])
                    continue;
                cctv.visited[i] = true;
                DFS_recursion(depth + 1, i);
                cctv.visited[i] = false;
            }
        }
    }

    private static int minZeroCnt(HashSet<Integer> set){
        int minVal = 100;
        Iterator iterator = set.iterator();
        while(iterator.hasNext()){
            int val = (Integer)iterator.next();
            if(val < minVal)
                minVal = val;
        }
        return minVal;
    }

    private static int printRoomAndCountZero(int[][] arr){
        int cnt = 0;
        for (int i = 0; i < arr.length; i++){
            for (int j = 0; j < arr[i].length; j++){
                if (arr[i][j] == 0)
                    cnt++;
            }
        }
        return cnt;
    }

    private static void getBack7to0(int[][] arr){
        for (int i = 0; i < arr.length; i++){
            for (int j = 0; j < arr[i].length; j++){
                if (arr[i][j] == 7)
                    arr[i][j] = 0;
            }
        }
    }

    private static void mark7(int cctvType, int direction, int x, int y){
        switch (cctvType) {
            case 1:
                switch (direction) {
                    case 0://up
                        mark7Up(x,y);
                        break;
                    case 1://right
                        mark7Right(x,y);
                        break;
                    case 2://down
                        mark7Down(x,y);
                        break;
                    case 3://left
                        mark7Left(x,y);
                        break;
                }
                break;
            case 2:
                switch (direction) {
                    case 0://up
                        mark7Up(x,y);
                        mark7Down(x,y);
                        break;
                    case 1://right
                        mark7Left(x,y);
                        mark7Right(x,y);
                        break;
                    case 2://down
                        mark7Up(x,y);
                        mark7Down(x,y);
                        break;
                    case 3://left
                        mark7Left(x,y);
                        mark7Right(x,y);
                        break;
                }
                break;
            case 3:
                switch (direction) {
                    case 0://up
                        mark7Up(x,y);
                        mark7Right(x,y);
                        break;
                    case 1://right
                        mark7Right(x,y);
                        mark7Down(x,y);
                        break;
                    case 2://down
                        mark7Down(x,y);
                        mark7Left(x,y);
                        break;
                    case 3://left
                        mark7Left(x,y);
                        mark7Up(x,y);
                        break;
                }
                break;
            case 4:
                switch (direction) {
                    case 0://up
                        mark7Left(x,y);
                        mark7Up(x,y);
                        mark7Right(x,y);
                        break;
                    case 1://right
                        mark7Up(x,y);
                        mark7Right(x,y);
                        mark7Down(x,y);
                        break;
                    case 2://down
                        mark7Right(x,y);
                        mark7Down(x,y);
                        mark7Left(x,y);
                        break;
                    case 3://left
                        mark7Down(x,y);
                        mark7Left(x,y);
                        mark7Up(x,y);
                        break;
                }
                break;
            case 5:
                switch (direction) {
                    case 0://up
                        mark7Up(x,y);
                        mark7Right(x,y);
                        mark7Left(x,y);
                        mark7Down(x,y);
                        break;
                    case 1://right
                        mark7Up(x,y);
                        mark7Right(x,y);
                        mark7Left(x,y);
                        mark7Down(x,y);
                        break;
                    case 2://down
                        mark7Up(x,y);
                        mark7Right(x,y);
                        mark7Left(x,y);
                        mark7Down(x,y);
                        break;
                    case 3://left
                        mark7Up(x,y);
                        mark7Right(x,y);
                        mark7Left(x,y);
                        mark7Down(x,y);
                        break;
                }
                break;
        }
    }
    private static void mark7Up(int x, int y) {
        for (int i = x-1; i > -1; i--){
            if(room[i][y] == 6)
                break;
            if(room[i][y] == 1 || room[i][y] == 2 || room[i][y] == 3 || room[i][y] == 4 || room[i][y] == 5)
                continue;
            room[i][y] = 7;
        }
    }
    private static void mark7Right(int x, int y) {
        for (int i = y+1; i < room[x].length; i++){
            if(room[x][i] == 6)
                break;
            if(room[x][i] == 1 || room[x][i] == 2 || room[x][i] == 3 || room[x][i] == 4 || room[x][i] == 5)
                continue;
            room[x][i] = 7;
        }
    }
    private static void mark7Down(int x, int y) {
        for (int i = x+1; i < room.length; i++){
            if(room[i][y] == 6)
                break;
            if(room[i][y] == 1 || room[i][y] == 2 || room[i][y] == 3 || room[i][y] == 4 || room[i][y] == 5)
                continue;
            room[i][y] = 7;
        }
    }
    private static void mark7Left(int x, int y) {
        for (int i = y-1; i > -1; i--){
            if(room[x][i] == 6)
                break;
            if(room[x][i] == 1 || room[x][i] == 2 || room[x][i] == 3 || room[x][i] == 4 || room[x][i] == 5)
                continue;
            room[x][i] = 7;
        }
    }

}

댓글

이 블로그의 인기 게시물

About JVM Warm up

About idempotent

About Kafka Basic

About ZGC

sneak peek jitpack

Spring Boot Actuator readiness, liveness probes on k8s

About Websocket minimize data size and data transfer cost on cloud

About G1 GC

대학생 코딩 과제 대행 java, python, oracle 네 번째