• 백준 15683번 감시 :: 마이구미
    알고리즘 풀이/브루트 포스 2018. 4. 28. 18:15
    반응형

    이 글은 백준 알고리즘 문제 15683번 "감시" 를 풀이한다.

    2018 삼성 SW 역량 테스트 문제이다.

    접근 방법은 브루트포스와 DFS 를 통해 풀이한다.

    문제 링크 - https://www.acmicpc.net/problem/15683

    DFS - http://mygumi.tistory.com/102


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

    1번2번3번4번5번

    1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.

    CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.

    CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.



    문제 해결을 위해서는 모든 경우를 전부 확인하면 되는 문제이다.

    문제는 크게 어렵지 않지만, 구현이 단순하지는 않는 문제이다. 

    항상 이런 유형을 내고 있는 것으로 보인다.


    문제는 크게 다음과 같다.


    1. 총 5개의 CCTV 가 존재하는데, 각 CCTV 는 감시할 수 있는 방향이 다르다.
    2. CCTV 는 90도 회전이 가능하다.
    3. CCTV 는 벽을 통과할 수 없지만, CCTV 는 통과할 수 있다.


    2번이 의미하는 것은 다음과 같다.


    15683번 감시15683번 감시


    위와 같은 형태로 90도 회전을 하기 때문에 1번은 단순히 오른쪽 방향만 감시하는 것이 아니다.

    결과적으로는 다음과 같이 감시할 수 있다.


    • 1번 CCTV - (오른쪽), (위쪽), (왼쪽), (아래쪽) => 4가지
    • 2번 CCTV - (왼쪽, 오른쪽), (위쪽, 아래쪽) => 2가지
    • 3번 CCTV - (위쪽, 오른쪽), (오른쪽, 아래쪽), (아래쪽, 왼쪽), (왼쪽, 위쪽) => 4가지
    • 4번 CCTV - (왼쪽, 위쪽, 오른쪽), (위쪽, 오른쪽, 아래쪽), (오른쪽, 아래쪽, 왼쪽), (아래쪽, 왼쪽, 위쪽) => 4가지
    • 5번 CCTV - (왼쪽, 위쪽, 오른쪽, 아래쪽) => 1가지


    위의 모든 경우를 위해 DFS 와 같이 재귀적으로 모든 경우를 탐색한다.


    public static void search(int cctvIndex, int[][] prev) { int[][] visited = new int[n][m]; if (cctvIndex == list.size()) { // 모든 CCTV 탐색했을 경우 // 사각지대 갯수 카운트 } else {

    ........... switch (idx) { case 1: for (int k = 0; k < 4; k++) { for (int i = 0; i < n; i++) { // 이전 감시 현황 가져옴 visited[i] = Arrays.copyOf(prev[i], m); } detect(visited, y, x, k); // 감시여부 체크 search(cctvIndex + 1, visited); // 다음 CCTV 탐색 } break; case 2: case 3: case 4: case 5: } } }


    위 코드가 실질적인 코드이다.


    1. 이전 감시 현황(prev)을 가져온다.

    2. CCTV 감시한다.

    3. 다음 CCTV 를 탐색한다.


    * 각 경우에서 감시된 현황을 위해 매번 탐색할 때마다 깊은 복사를 사용한다. (prev -> visited)


    Github - https://github.com/hotehrud/acmicpc/blob/master/SAMSUMG/15683.java


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    static int n, m, ans = Integer.MAX_VALUE;
    static int[][] map;
    static ArrayList<Node> list = new ArrayList<Node>();
     
    private void solve() {
        n = sc.nextInt();
        m = sc.nextInt();
        map = new int[n][m];
     
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int v = sc.nextInt();
                map[i][j] = v;
                if (<= v && v <= 5) {
                    list.add(new Node(i, j, v));
                }
            }
        }
        search(0, map);
        System.out.println(ans);
    }
     
    public static void search(int cctvIndex, int[][] prev) {
        int[][] visited = new int[n][m];
        if (cctvIndex == list.size()) {
            int temp = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (prev[i][j] == 0) {
                        temp++;
                    }
                }
            }
            if (temp < ans) {
                ans = temp;
            }
        } else {
            Node node = list.get(cctvIndex);
            int idx = node.idx;
            int x = node.x;
            int y = node.y;
     
            switch (idx) {
                case 1:
                    for (int k = 0; k < 4; k++) {
                        for (int i = 0; i < n; i++) {
                            visited[i] = Arrays.copyOf(prev[i], m);
                        }
                        detect(visited, y, x, k);
                        search(cctvIndex + 1, visited);
                    }
                    break;
                case 2:
                    for (int k = 0; k < 2; k++) {
                        for (int i = 0; i < n; i++) {
                            visited[i] = Arrays.copyOf(prev[i], m);
                        }
                        detect(visited, y, x, k);
                        detect(visited, y, x, k + 2);
                        search(cctvIndex + 1, visited);
                    }
                    break;
                case 3:
                    for (int k = 0; k < 4; k++) {
                        for (int i = 0; i < n; i++) {
                            visited[i] = Arrays.copyOf(prev[i], m);
                        }
                        detect(visited, y, x, k);
                        detect(visited, y, x, (k + 1) % 4);
                        search(cctvIndex + 1, visited);
                    }
                    break;
                case 4:
                    for (int k = 0; k < 4; k++) {
                        for (int i = 0; i < n; i++) {
                            visited[i] = Arrays.copyOf(prev[i], m);
                        }
                        detect(visited, y, x, k);
                        detect(visited, y, x, (k + 1) % 4);
                        detect(visited, y, x, (k + 2) % 4);
                        search(cctvIndex + 1, visited);
                    }
                    break;
                case 5:
                    for (int i = 0; i < n; i++) {
                        visited[i] = Arrays.copyOf(prev[i], m);
                    }
                    detect(visited, y, x, 0);
                    detect(visited, y, x, 1);
                    detect(visited, y, x, 2);
                    detect(visited, y, x, 3);
                    search(cctvIndex + 1, visited);
                    break;
            }
        }
    }
     
    public static void detect(int[][] visited, int i, int j, int direction) {
        switch (direction) {
            case 0:
                for (int k = j; k >= 0; k--) {
                    if (map[i][k] == 6) {
                        break;
                    }
                    visited[i][k] = 7;
                }
                break;
            case 1:
                for (int k = i; k >= 0; k--) {
                    if (map[k][j] == 6) {
                        break;
                    }
                    visited[k][j] = 7;
                }
                break;
            case 2:
                for (int k = j; k < m; k++) {
                    if (map[i][k] == 6) {
                        break;
                    }
                    visited[i][k] = 7;
                }
                break;
            case 3:
                for (int k = i; k < n; k++) {
                    if (map[k][j] == 6) {
                        break;
                    }
                    visited[k][j] = 7;
                }
                break;
        }
    }
     
    public static class Node {
        int x;
        int y;
        int idx;
     
        Node(int y, int x, int idx) {
            this.x = x;
            this.y = y;
            this.idx = idx;
        }
    }
    cs


    반응형

    댓글

Designed by Tistory.