[Java] 백준 15683 - 감시

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

 

1~5번 cctv의 모든 각도의 경우의 수를 구해야 하는 문제이었고, DFS로 풀었다.

삼성 문제답게 구현이 너무나 힘들었지만 1시간 반정도 걸려서 정답을 낼 수 있었다. 뭐랄까 구현 난이도가 그렇게 까지 높진 않지만 할게 많다는 느낌? 실전에서도 충분히 나올 수 있는 유형인 만큼 익숙해지면 좋다고 생각한다.

 

시나리오

1. 2차원 배열로 \(N * M \)그리드 입력받기.
2. 최초 1회 그리드 탐색해서 CCTV의 개수와 좌표 파악.
3. 구해놓은 좌표 list를 순차적으로 돌며 각 요소에 해당하는 cctv의 모든 각도를 구한다.
4. 3의 과정을 dfs함수내에서 수행하며, 하나의 cctv에 대해 \(0^\circ, 90^\circ, 180^\circ, 270^\circ\) 중 하나의 각도가 정해졌다면 각도와 cctv의 종류를 고려하여 그리드의 '#'을 채운다.
5. dfs함수를 재귀호출하여 depth가 cctv의 개수와 같아질 때 사각지대의 최솟값을 구한다. 이때 기존의 값보다 작다면 갱신.
6. dfs함수를 빠져나왔을 땐 이전 상태로 되돌리는 백트래킹 작업이 필요하며 이는 \(N * M\) 그리드 2차원 배열을 깊은 복사하여 해결한다.

 

내 코드

import java.util.*;
import java.io.*;

public class Main {
    private static int N;
    private static int M;
    private static int cctvCnt;
    private static List<List<Integer>> cctvCoordi = new ArrayList<>();
    private static String[][] grid;
    private static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        grid = new String[N][M];
        ////1. 입력받아 2차원 grid
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                grid[i][j] = st.nextToken();
                if (countCCTV(grid[i][j])) {
                    cctvCoordi.add(List.of(i, j));
                }
            }
        }
        dfs(0, 0);
        System.out.println(answer);
    }

    //2차원 배열 클론
    private static String[][] cloneGrid() {
        String[][] newGrid = new String[N][M];
        for (int i = 0; i < N; i++) {
            newGrid[i] = grid[i].clone();
        }
        return newGrid;
    }

    //cctv개수 카운트
    private static boolean countCCTV(String input) {
        char[] charArr = input.toCharArray();
        if (Character.isDigit(charArr[0])) {
            int num = charArr[0] - 48;
            if (1 <= num && num <= 5) {
                cctvCnt++;
                return true;
            }
        }
        return false;
    }

    ////2. dfs로 구현, 이중 for문 돌며 1~5를 발견했을 때, grid에 #을 찍고 depth+1. 다음 숫자 찾아서 반복.
    // 그리드를 전부 탐색(=주어진 cctv개수만큼 depth를 들어왔을 때) 했을 때 0의 개수 카운트해서 min값 갱신
    // 주의! dfs가 return됐을 때 이전 그리드 상태로 돌려놔야함
    private static void dfs(int d, int iter) {
        if (d == cctvCnt) {
            answer = Math.min(answer, cntZero());
            return;
        }
        for (int i = iter; i < cctvCoordi.size(); i++) {
            List<Integer> currentCoordi = cctvCoordi.get(i);
            int kindOfCctv = Integer.parseInt(grid[currentCoordi.get(0)][currentCoordi.get(1)]);
            if (kindOfCctv == 1) {
                for (int k = 0; k < 4; k++) {
                    //그리기 전 이전 상태 저장
                    String[][] newGrid = cloneGrid();
                    //90도 씩 네번
                    drawRange(k, currentCoordi, kindOfCctv);
                    dfs(d + 1, i + 1);
                    //dfs리턴 후 원상복구
                    grid = newGrid;
                }
            } else if (kindOfCctv == 2) {
                for (int k = 0; k < 2; k++) {
                    String[][] newGrid = cloneGrid();
                    //90도 씩 두번
                    drawRange(k, currentCoordi, kindOfCctv);
                    dfs(d + 1, i + 1);
                    grid = newGrid;
                }
            } else if (kindOfCctv == 3) {
                for (int k = 0; k < 4; k++) {
                    String[][] newGrid = cloneGrid();
                    //90도 씩 네번
                    drawRange(k, currentCoordi, kindOfCctv);
                    dfs(d + 1, i + 1);
                    grid = newGrid;
                }
            } else if (kindOfCctv == 4) {
                for (int k = 0; k < 4; k++) {
                    String[][] newGrid = cloneGrid();
                    //90도 씩 네번
                    drawRange(k, currentCoordi, kindOfCctv);
                    dfs(d + 1, i + 1);
                    grid = newGrid;
                }
            } else {
                String[][] newGrid = cloneGrid();
                //90도 씩 한번
                drawRange(5, currentCoordi, kindOfCctv);
                dfs(d + 1, i + 1);
                grid = newGrid;
            }
            dfs(d + 1, i + 1);
            grid = cloneGrid();
        }
    }

    //3. 1~5일 때, grid에 #을 찍는 함수
    private static void drawRange(int angle, List<Integer> currentCoordi, int cctv) {
        int currentRow = currentCoordi.get(0);
        int currentCol = currentCoordi.get(1);

        //필요한 것 현재 좌표
        if (cctv == 1) {
            //우
            if (angle == 0) {
                rightDraw(currentRow, currentCol);
            }//좌
            else if (angle == 1) {
                leftDraw(currentRow, currentCol);
            }//하
            else if (angle == 2) {
                downDraw(currentRow, currentCol);
            } //상
            else {
                upDraw(currentRow, currentCol);
            }
            return;
        }
        if (cctv == 2) {
            if (angle == 0) {
                //우
                leftDraw(currentRow, currentCol);
                //좌
                rightDraw(currentRow, currentCol);

            } else if (angle == 1) {
                //하
                downDraw(currentRow, currentCol);
                //상
                upDraw(currentRow, currentCol);
            }
            return;
        }
        if (cctv == 3) {
            if (angle == 0) {
                //상, 우
                upDraw(currentRow, currentCol);
                rightDraw(currentRow, currentCol);
            } else if (angle == 1) {
                //우, 하
                rightDraw(currentRow, currentCol);
                downDraw(currentRow, currentCol);
            } else if (angle == 2) {
                //좌, 하
                leftDraw(currentRow, currentCol);
                downDraw(currentRow, currentCol);
            } else {
                //좌, 상
                leftDraw(currentRow, currentCol);
                upDraw(currentRow, currentCol);
            }
            return;
        }
        if (cctv == 4) {
            //좌, 상, 우
            if (angle == 0) {
                leftDraw(currentRow, currentCol);
                upDraw(currentRow, currentCol);
                rightDraw(currentRow, currentCol);
            }
            //상, 우, 하
            else if (angle == 1) {
                upDraw(currentRow, currentCol);
                rightDraw(currentRow, currentCol);
                downDraw(currentRow, currentCol);
            }//우, 하, 좌
            else if (angle == 2) {
                rightDraw(currentRow, currentCol);
                downDraw(currentRow, currentCol);
                leftDraw(currentRow, currentCol);
            }
            //하, 좌, 상
            else {
                downDraw(currentRow, currentCol);
                leftDraw(currentRow, currentCol);
                upDraw(currentRow, currentCol);
            }
            return;
        }
        //상, 하, 좌, 우
        upDraw(currentRow, currentCol);
        downDraw(currentRow, currentCol);
        leftDraw(currentRow, currentCol);
        rightDraw(currentRow, currentCol);
    }

    private static void leftDraw(int currentRow, int currentCol) {
        for (int i = currentCol - 1; i >= 0; i--) {
            if (grid[currentRow][i].equals("0")) {
                grid[currentRow][i] = "#";
                continue;
            }
            if (grid[currentRow][i].equals("6")) {
                break;
            }
        }
    }

    private static void rightDraw(int currentRow, int currentCol) {
        for (int i = currentCol + 1; i < M; i++) {
            if (grid[currentRow][i].equals("0")) {
                grid[currentRow][i] = "#";
                continue;
            }
            if (grid[currentRow][i].equals("6")) {
                break;
            }
        }
    }

    private static void downDraw(int currentRow, int currentCol) {
        for (int i = currentRow + 1; i < N; i++) {
            if (grid[i][currentCol].equals("0")) {
                grid[i][currentCol] = "#";
                continue;
            }
            if (grid[i][currentCol].equals("6")) {
                break;
            }
        }
    }

    private static void upDraw(int currentRow, int currentCol) {
        for (int i = currentRow - 1; i >= 0; i--) {
            if (grid[i][currentCol].equals("0")) {
                grid[i][currentCol] = "#";
                continue;
            }
            if (grid[i][currentCol].equals("6")) {
                break;
            }
        }
    }

    private static int cntZero() {
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (grid[i][j].equals("0")) {
                    cnt++;
                }
            }
        }
        return cnt;
    }
}

//    /**
//     * cctv 방향을 적절하게 정해서 사각 지대의 최소 크기를 구하자.
//     * 사각지대 = cctv가 감시하는 방향을 최대로 설정했을 때 남는 0의 개수
//     */

새로 알게된 점 || 리마인더

배열의 깊은 복사

배열의 깊은 복사는 다음 세가지 메서드로 구현가능하다. 익숙해져서 구글링없이도 사용할 수 있도록 하자.

//System.arrayCopy()
int[] sourceArray = {1, 2, 3, 4, 5};
int[] targetArray = new int[sourceArray.length];

System.arraycopy(sourceArray, 0, targetArray, 0, sourceArray.length);

//Arrays.copyOf()
int[] sourceArray = {1, 2, 3, 4, 5};
int[] targetArray = Arrays.copyOf(sourceArray, sourceArray.length);

//Object.clone()
int[] sourceArray = {1, 2, 3, 4, 5};
int[] targetArray = sourceArray.clone();

 

숫자의 아스키 코드는 48~57

String을 char로 바꿔 Character.isDigit()를 사용하거나 할 때 char 데이터 타입을 사용하곤 한다.

위 메서드를 사용하면 보통은 정수연산을 하기 마련인데, 이 때 char형을 int에 집어넣을 때는 ascii값이 들어가기 때문에 -48을 해주어 집어넣도록 하자.

참고로 ascii코드에는 0~9까지 숫자만 등록이 되어 있고 그 이상의 char값을 int로 변환하면 가장 앞자리수에 해당하는 ascii코드값을 집어넣게 된다.

    public static void main(String[] args) {
        String[] nums = {"9","10","11","12","13","14","15","16","100","1000","2345","22","33","44","5555"};
        for (String num : nums) {
            char[] charArr = num.toCharArray();
            int toInt = charArr[0]-48;
            //9 1	1	1	1	1	1	1	1	1	2	2	3	4	5	
            System.out.print(toInt+"\t");
        }
    }