[백준][삼성 SW 역량 테스트][Gold 5][C++] 15683 감시

문제

백준 삼성 SW 역량 테스트 기출 문제 - 15683 감시 (Gold 5)

15683번: 감시

 

---

문제 풀이

접근 방식

이 문제는 CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 문제이다.

CCTV는 아래와 같이 번호에 따라 감시하는 방향이 다르다.

 

 

어느 방향으로 CCTV를 설치했을 때 사각 지대가 최소가 되는 지 구하는 문제이기 때문에,

DFS 함수를 만들어 모든 CCTV의 설치 방향(4방향)에 따른 사각 지대의 크기를 구해주었다.

 

DFS 함수에서 모든 CCTV의 방향을 정하였을 때,

go 함수를 통해 CCTV가 감시할 수 있는 모든 영역을 표시해주었다.

이 때, CCTV는 번호에 따라 감시 방향이 다르기 때문에 각각을 하드코딩으로 구현해주었다.

그리고 count 함수를 만들어 사각 지대의 크기를 구해주었다.

 

---

풀이 코드 - C++

#include <iostream>
#include <vector>

using namespace std;

struct CCTV {
    int x;
    int y;
    int n;
};

int N, M, len;
int MIN = 987654321;
vector<vector<int>> map;
vector<vector<int>> copy_map;
vector<CCTV> cctvs;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

int count() {
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 0)
                cnt++;
        }
    }
    return cnt;
}

void go(vector<int> dirs) {
    for (int i = 0; i < len; i++) {
        int x = cctvs[i].x;
        int y = cctvs[i].y;
        int n = cctvs[i].n;
        switch (n) {
        case 1: // CCTV 1
            while (1) {
                x += dir[dirs[i]][0];
                y += dir[dirs[i]][1];
                if (x < 0 || x >= N || y < 0 || y >= M || map[x][y] == 6) break;
                map[x][y] = n;
            }
            break;
        case 2: // CCTV 2
            while (1) {
                x += dir[dirs[i]][0];
                y += dir[dirs[i]][1];
                if (x < 0 || x >= N || y < 0 || y >= M || map[x][y] == 6) break;
                map[x][y] = n;
            }
            x = cctvs[i].x;
            y = cctvs[i].y;
            while (1) {
                x += dir[(dirs[i] + 2) % 4][0];
                y += dir[(dirs[i] + 2) % 4][1];
                if (x < 0 || x >= N || y < 0 || y >= M || map[x][y] == 6) break;
                map[x][y] = n;
            }
            break;
        case 3: // CCTV 3
            while (1) {
                x += dir[dirs[i]][0];
                y += dir[dirs[i]][1];
                if (x < 0 || x >= N || y < 0 || y >= M || map[x][y] == 6) break;
                map[x][y] = n;
            }
            x = cctvs[i].x;
            y = cctvs[i].y;
            while (1) {
                x += dir[(dirs[i] + 3) % 4][0];
                y += dir[(dirs[i] + 3) % 4][1];
                if (x < 0 || x >= N || y < 0 || y >= M || map[x][y] == 6) break;
                map[x][y] = n;
            }
            break;
        case 4: // CCTV 4
            while (1) {
                x += dir[dirs[i]][0];
                y += dir[dirs[i]][1];
                if (x < 0 || x >= N || y < 0 || y >= M || map[x][y] == 6) break;
                map[x][y] = n;
            }
            x = cctvs[i].x;
            y = cctvs[i].y;
            while (1) {
                x += dir[(dirs[i] + 2) % 4][0];
                y += dir[(dirs[i] + 2) % 4][1];
                if (x < 0 || x >= N || y < 0 || y >= M || map[x][y] == 6) break;
                map[x][y] = n;
            }
            x = cctvs[i].x;
            y = cctvs[i].y;
            while (1) {
                x += dir[(dirs[i] + 3) % 4][0];
                y += dir[(dirs[i] + 3) % 4][1];
                if (x < 0 || x >= N || y < 0 || y >= M || map[x][y] == 6) break;
                map[x][y] = n;
            }
            break;
        case 5: // CCTV 5
            while (1) {
                x += dir[0][0];
                y += dir[0][1];
                if (x < 0 || x >= N || y < 0 || y >= M || map[x][y] == 6) break;
                map[x][y] = n;
            }
            x = cctvs[i].x;
            y = cctvs[i].y;
            while (1) {
                x += dir[1][0];
                y += dir[1][1];
                if (x < 0 || x >= N || y < 0 || y >= M || map[x][y] == 6) break;
                map[x][y] = n;
            }
            x = cctvs[i].x;
            y = cctvs[i].y;
            while (1) {
                x += dir[2][0];
                y += dir[2][1];
                if (x < 0 || x >= N || y < 0 || y >= M || map[x][y] == 6) break;
                map[x][y] = n;
            }
            x = cctvs[i].x;
            y = cctvs[i].y;
            while (1) {
                x += dir[3][0];
                y += dir[3][1];
                if (x < 0 || x >= N || y < 0 || y >= M || map[x][y] == 6) break;
                map[x][y] = n;
            }
            break;
        }
    }
}

void DFS(int cnt, vector<int> dirs) {
    if (cnt == len) {
        go(dirs);
        int result = count();
        if (MIN > result) MIN = result;
        map = copy_map;
        return;
    }
    for (int i = 0; i < 4; i++) {
        dirs[cnt] = i;
        DFS(cnt + 1, dirs);
    }
}

int main() {
    // 입력 받기
    cin >> N >> M;
    map.assign(N, vector<int>(M));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
            if (map[i][j] >= 1 && map[i][j] <= 5)
                cctvs.push_back({i, j, map[i][j]});
        }
    }
    copy_map = map;

    // 모든 방향 탐색하여 최소 사각 지대 구하기
    len = cctvs.size();
    vector<int> dirs(len);
    DFS(0, dirs);
    cout << MIN;
}

실행 결과

실행 결과 : 통과 (32ms)