[Algorithm] SW 기출문제 - 감시(15683) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 백준 SW 기출문제 - 감시 자바 풀이를 진행하고자 합니다.

 

문제 출처: https://www.acmicpc.net/problem/15683

15683번: 감시

 

 

1. 풀이 소스:

 

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

import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());
        Cctv cctv = new Cctv(n, m); // 인스턴스 생성
        
        for (int row = 0; row < n; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 0; col < m; col++)
                cctv.setMap(row, col, parseInt(st.nextToken()));
        }
        
        cctv.build();
        
        System.out.println(cctv.getMinNonSafeRegion());
    }
}

class Cctv {
    
    static final int[] DR = {-1, 0, 1, 0, -1, 0}; // -1, 0, 1, 0 에 추가로 -1, 0 을 넣은 이유 참조 #1
    static final int[] DC = {0, -1, 0, 1, 0, -1};
    
    int n; // row 총 개수
    int m; // col 총 개수
    int safeCnt; // 벽과 cctv 개수를 포함한 개수
    int maxSafeCnt; // 최고 안전 지대 개수
    int[][] map;
    List<Point> cctvs = new ArrayList<>(); // cctv를 저장할 리스트
    
    Cctv (int n, int m) {
        this.n = n;
        this.m = m;
        map = new int[n][m];
    }
    
    void setMap(int row, int col, int value) {
        map[row][col] = value;
        
        if (value != 0) safeCnt++; // 만약 cctv 혹은 벽이라면 안전지대 개수 추가
        if (value != 0 && value != 6) cctvs.add(new Point(row, col)); // cctv 추가
    }
    
    void build() {
        if (cctvs.isEmpty()) { // cctv가 없을 수 있으므로 safeCnt 바로 maxSafeCnt로 할당하고 종료
            maxSafeCnt = safeCnt;
            return;
        }

        boolean[][] nowVisited = new boolean[n][m]; // 방문 위치 설정
        int nowSafeCnt = safeCnt; // nowSafeCnt로 지역변수 설정 후 재귀
        dfs(0, nowSafeCnt, nowVisited);
    }

    // idx: cctv 리스트를 순회할 인덱스, preSafeCnt: 이전 재귀에서 얻은 안전지대 개수, preVisited: 이전 재귀에서 방문한 곳
    void dfs(int idx, int preSafeCnt, boolean[][] preVisited) {
        if (idx == cctvs.size()) { // 만약 모든 cctv를 전부 탐색했다면
            maxSafeCnt = Math.max(preSafeCnt, maxSafeCnt);
            return; // 최대값 업데이트 후 종료
        }
        Point p = cctvs.get(idx); // 인덱스로 cctv 포인트 가져오기
        int row = p.row;
        int col = p.col;
        int value = map[row][col];

        if (value == 1) { // 1번 시시티비라면
            for (int k = 0; k < 4; k++) { // 상 하 좌 우 한 번만 이동 가능
                int nowSafeCnt = preSafeCnt; // nowSafeCnt로 지역 변수 할당 참조#2
                boolean[][] nowVisited = getNowVisited(preVisited); // preVisted를 깊은 복사한 nowVisited 생성
                nowSafeCnt = viewToDir(row, col, DR[k], DC[k], nowSafeCnt, nowVisited); // while문으로 벽이 나올 때까지 탐색 참조#3
                dfs(idx + 1, nowSafeCnt, nowVisited); // 재귀 실행
            }
        }

        else if (value == 2) {
            for (int k = 0; k < 2; k++) { // 짝 i = 0, i = 2 // i = 1, i = 3
                int nowSafeCnt = preSafeCnt;
                boolean[][] nowVisited = getNowVisited(preVisited);
                for (int d = 0; d < 2; d++) // 2번은 '좌우' 혹은 '상하'가 짝이므로 이중 포문으로 짝이 나올 수 있도록 2d + k 설정
                    nowSafeCnt = viewToDir(row, col, DR[k + 2 * d], DC[k + 2 * d], nowSafeCnt, nowVisited);
                dfs(idx + 1, nowSafeCnt, nowVisited);
            }
        }

        else if (value == 3) {
            for (int k = 0; k < 4; k++) {
                int nowSafeCnt = preSafeCnt;
                boolean[][] nowVisited = getNowVisited(preVisited);
                for (int d = 0; d < 2; d++) // 3번은 'ㄱ' 이 나와야 하므로 k + d로 '상좌', '좌하', '하우', '우상' 설정
                    nowSafeCnt = viewToDir(row, col, DR[k + d], DC[k + d], nowSafeCnt, nowVisited);
                dfs(idx + 1, nowSafeCnt, nowVisited);
            }
        }

        else if (value == 4) {
            for (int k = 0; k < 4; k++) {
                int nowSafeCnt = preSafeCnt;
                boolean[][] nowVisited = getNowVisited(preVisited);
                for (int d = 0; d < 3; d++) // 4번은 'ㅜ'가 나와야 하므로 k + d로  '상하좌', '상하우', '좌우상' '좌우하' 설정
                    nowSafeCnt = viewToDir(row, col, DR[k + d], DC[k + d], nowSafeCnt, nowVisited);
                dfs(idx + 1, nowSafeCnt, nowVisited);
            }
        }

        else {
            int nowSafeCnt = preSafeCnt;
            boolean[][] nowVisited = getNowVisited(preVisited);
            for (int k = 0; k < 4; k++) // 5번은 상하좌우 모두 탐색해야하므로 단일 포문으로 모두 탐색하도록 진행
                nowSafeCnt = viewToDir(row, col, DR[k], DC[k], nowSafeCnt, nowVisited);
            dfs(idx + 1, nowSafeCnt, nowVisited);
        }
    }

    // 유효한 인덱스에 row, col의 map 값이 벽이 아니여야함 (cctv는 통과 가능)
    boolean isValid(int row, int col) {
        return row >= 0 && row < n && col >= 0 && col < m && map[row][col] != 6;
    }

    int viewToDir(int row, int col, int dr, int dc, int nowSafeCnt, boolean[][] nowVisited) {
        while(true) {
            row += dr; // row에 값 업데이트
            col += dc; // col에 값 업데이트

            if (!isValid(row, col)) break; // 만약 벽이거나 유효한 인덱스가 아니라면 종료
            if (!nowVisited[row][col] && map[row][col] == 0) { // 방문하지 않은 경우에만
                nowVisited[row][col] = true;
                nowSafeCnt++;
            }
        }
        return nowSafeCnt;
    }

    boolean[][] getNowVisited(boolean[][] preVisited) { // 깊은 복사 진행
        boolean[][] nowVisited = new boolean[n][m];
        for (int r = 0; r < n; r++) nowVisited[r] = preVisited[r].clone();
        return nowVisited;
    }
    
    int getMinNonSafeRegion() {
        return n * m - maxSafeCnt;
    }
        
    static class Point {
        int row;
        int col;
        
        Point (int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}

 

 

2. 풀이 중점 사항

 

해당 문제는 정답률을 보았을 때, 쉬운 문제처럼 느껴질 수 있었지만 굉장히 복잡하고 실수를 유발하는 문제였습니다.

문제 자체는 이해가 빠르게 되었지만 이걸 어떻게 구현해야 할까라는 고민을 많이 하였습니다. 코드를 작성하는 과정에도 "잘못 풀고 있나?"라는 생각을 하면서 해결했던 것 같습니다.

 

먼저 이 문제는 5가지의 cctv를 다른 방법으로 탐색시켜야 했습니다. 따라서, DR, DC를 -1, 0, 1, 0 으로 설정하지 않고 다르게 설정하였습니다.

 

 

참조#1

 

static final int[] DR = {-1, 0, 1, 0, -1, 0}; // -1, 0, 1, 0 에 추가로 -1, 0 을 넣은 이유 참조 #1
static final int[] DC = {0, -1, 0, 1, 0, -1};

 

DR, DC를 다음과 같이 6개의 값으로 초기화 한 이유는  아래의 예시처럼 각각 다른 CCTV가 보이는 방향을 하나의 static final 배열의 DR, DC로 설정하기 위함입니다.

 

if (value == 1) { // 1번 시시티비라면
    for (int k = 0; k < 4; k++) { // 상 하 좌 우 한 번만 이동 가능
        int nowSafeCnt = preSafeCnt; // nowSafeCnt로 지역 변수 할당 참조#2
        boolean[][] nowVisited = getNowVisited(preVisited); // preVisted를 깊은 복사한 nowVisited 생성
        nowSafeCnt = viewToDir(row, col, DR[k], DC[k], nowSafeCnt, nowVisited); // while문으로 벽이 나올 때까지 탐색 참조#3
        dfs(idx + 1, nowSafeCnt, nowVisited); // 재귀 실행
    }
}

else if (value == 2) {
    for (int k = 0; k < 2; k++) { // 짝 i = 0, i = 2 // i = 1, i = 3
        int nowSafeCnt = preSafeCnt;
        boolean[][] nowVisited = getNowVisited(preVisited);
        for (int d = 0; d < 2; d++) // 2번은 '좌우' 혹은 '상하'가 짝이므로 이중 포문으로 짝이 나올 수 있도록 2d + k 설정
            nowSafeCnt = viewToDir(row, col, DR[k + 2 * d], DC[k + 2 * d], nowSafeCnt, nowVisited);
        dfs(idx + 1, nowSafeCnt, nowVisited);
    }
}

 

예를 들어 cctv 번호가 1번이라면, 상 하 좌 우 하나의 방향으로만 이동이 가능합니다. 따라서 for(int k = 0 ~) 단일 포문으로  viewToDir로 탐색을 진행하고 dfs를 적용할 수 있습니다.

 

하지만 cctv 번호가 2번이라면, '좌우', '상하'가 하나의 묶음입니다. 따라서, 이중 for문으로 

row가 위, 아래  // col이 좌, 우로 움직일 수 있도록 k + 2 * d로 인덱스를 설정하였습니다.

 

그 결과, 만약 k = 0라면,

if d == 0: k + 2 * d = 0         ----> DR[0] = -1, DC[0] = 0

if d == 1: k + 2 * d = 2         ----> DR[2] = 1,  DC[2] = 0 

 

좌우로 움직일 수 있는 공식을 만들 수 있었습니다.

이와 같은 방법으로 3, 4, 5 를 처리하면 DR, DC 로 모든 경우를 처리할 수 있습니다.

 

 

참조 #2

 

else if (value == 2) {
    for (int k = 0; k < 2; k++) { // 짝 i = 0, i = 2 // i = 1, i = 3
        int nowSafeCnt = preSafeCnt;
        boolean[][] nowVisited = getNowVisited(preVisited);
        for (int d = 0; d < 2; d++) // 2번은 '좌우' 혹은 '상하'가 짝이므로 이중 포문으로 짝이 나올 수 있도록 2d + k 설정
            nowSafeCnt = viewToDir(row, col, DR[k + 2 * d], DC[k + 2 * d], nowSafeCnt, nowVisited);
        dfs(idx + 1, nowSafeCnt, nowVisited);
    }
}

 

이 코드를 살펴보면, nowSafeCnt로 지역변수를 바깥 for문 내에서 적용하는 것을 볼 수 있습니다. 

안쪽의 for (int d = 0 ~ )는 cctv가 탐색할 수 있는 방향의 묶음이므로

nowSafeCnt, nowVisited에 한 묶음이 모두 영향을 받아야 합니다.

 

하지만, k가 바뀐다면, 이는 곧 아예 탐색하는 방법을 바꾸는 것을 의미합니다.

즉, k = 0 이라면 좌우를 의미하는데, k = 1이라면 상하를 의미합니다.

 

따라서, 회전은 다른 경우의 수로 보아야 하기 때문에 독립성을 보장받아야 합니다. 이전의 nowSafeCnt는 영향을 주면 안 되므로 preSafeCnt를 재할당하고, preVisited를 깊은 복사 하여 for문의 이전 인덱스에 변경된 값이 영향을 주지 않도록 해야 합니다.

 

 

참조 #3

 

int viewToDir(int row, int col, int dr, int dc, int nowSafeCnt, boolean[][] nowVisited) {
    while(true) {
        row += dr; // row에 값 업데이트
        col += dc; // col에 값 업데이트

        if (!isValid(row, col)) break; // 만약 벽이거나 유효한 인덱스가 아니라면 종료
        if (!nowVisited[row][col] && map[row][col] == 0) { // 방문하지 않은 경우에만 참조#4
            nowVisited[row][col] = true;
            nowSafeCnt++;
        }
    }
    return nowSafeCnt;
}

 

row, col은 행과 열을 의미하고, dr dc는 DR, DC로 이동한 값을 의미합니다. 

while문으로 row, col을 업데이트하되, 만약 유효한 인덱스가 아니거나, 벽을 만난다면 break 하여 더 이상 방문 처리가 되지 않도록 합니다. 만약 아직 방문하지 않았고, map 값이 0이라면 nowSafeCnt를 1 추가합니다. 

 

여기서, 중요한 점은 '방문'이라는 것입니다. 방문하지 않은 경우에만 nowSafeCnt를 증가시키는 이유는 

5와 2가 인접한 경우  ### 5 2 ###   처럼 5 와 2는 같은 방향을 공유할 수 있기 때문입니다. 

따라서, 중복을 방지하기 위해 방문하지 않은 경우만 ++할 수 있도록 하였습니다.

 

 

이상으로 SW 기출문제 감시 - 자바 풀이를 마치도록 하겠습니다.

감사합니다.!