Taxol

I’ve always been.

백준 15683 - 감시

Updated:

C++

15683 번 - 감시

문제

사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오. 문제 출처

접근 방법

  1. 먼저 모든 cctv의 정보(위치, 타입)을 저장한다.
  2. DFS를 이용하여 cctv가 바라보는 방향을 모든 경우로 설정해준다. - 이의 경우 cctv의 방향과 상관없이 시계방향으로 한번씩 돌려준다고 생각하면 된다.
  3. 이제 cctv의 정보를 통하여 하나씩 감시방향을 설정해 준다.
  4. 각 cctv들이 감시하였다고 표시한 지도를 통하여 사각지대의 수를 찾는다.
  5. 다시 초기 지도의 상태로 돌아가 다음 경우의 수로 사각지대의 수를 찾는다.

구현

Main()

지도를 하나씩 graph에 넣으면서, 만약 cctv가 인식이 되면 cctv에 좌표와 그 cctv의 타입을 저장한다. 또한 direct에 방향을 설정하는데 초기는 오른쪽을 나타내는 0을 저장한다. direct는 0, 1, 2, 3까지 저장되며, 차례대로 오른쪽에서 부터 시계방향으로 돈다고 생각한다.

DFS()

DFS의 조건으로 cctv의 개수 만큼 설정하였을 때, Cal()함수를 호출하게 하였다. 모든 cctv를 다 사용하며, 각 cctv의 할당한 순서는 같으므로, 변수 cctv와 direct의 인덱스가 같다고 생각하면 된다.

Cal()

cctv들의 좌표와 타입, 그리고 방향을 하나씩 받아 어느 위치에 감시할 것인지 설정하는 함수이다. 각 타입에 따라 switch - case를 사용하여 구분한다. 각 타입은 현 위치에서 감시하는 방향을 (drt) 돌리면서 구현한다. 예를 들어, type 2인 경우 현재 방향에서 한번, 반대 편으로 한번 쭉 일자로 감시를 하며, type 4인 경우 시게 방향으로 3번 cctv 화면을 돌려서 감시를 한다. drt는 0, 1, 2, 3 중에 하나이며, 각 타입에 따라 drt를 변경해준다. 또한 4를 넘지 않게 해준다.

watch()

cctv 위치에서 drt 방향으로 벽을 만날 때 까지 일자로 7로 만들어 주며 감시를 구현한다.

getResult()

사각지대를 찾으며, 가장 적은 사각 지대 일 때 result를 갱신한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX 1e9
int n, m, result = MAX;
int graph[8][8];                            //지도
int saved[8][8];                            //백업 지도
vector<pair<pair<int, int>, int>> cctv;     //cctv의 위치와 타입을 저장 하는 객체
vector<int> direct;                         //cctv가 바라보는 방향
int dy[4] = { 0, 1, 0, -1 };                //우, 하, 좌, 상
int dx[4] = { 1, 0, -1, 0 };

void DFS(int lv);                           //각 cctv들의 방향을 설정하는 DFS
void Cal();                                 //cctv의 정보와 방향을 통해 감시 지역을 설정하는 함수
void watch(int y, int x, int drt);          //받은 정보를 통해 감시지역을 계산하는 함수
void copyGraph();                           //지도 초기화
void getResult();                           //0의 수를 세어, 사각지대의 수를 계산

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    cin >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> graph[i][j];
            saved[i][j] = graph[i][j];
            if (graph[i][j] > 0 && graph[i][j] != 6) {
                cctv.push_back(make_pair(make_pair(i, j), graph[i][j]));
                direct.push_back(0);
            }
        }
    }

    DFS(0);
    cout << result;
    return 0;
}

void DFS(int lv) {
    if (lv == cctv.size()) {
        Cal();
        getResult();
        copyGraph();
        return;
    }
    for (int j = 0; j < 4; j++) {
        direct.at(lv) = j;
        DFS(lv + 1);
    }
}

void Cal() {
    for (int i = 0; i < cctv.size(); i++) {
        int y = cctv.at(i).first.first;
        int x = cctv.at(i).first.second;
        int type = cctv.at(i).second;
        int drt = direct.at(i);
        switch (type) {
        case 1:
            watch(y, x, drt);
            break;
        case 2:
            for (int i = 0; i < 2; i++) {
                watch(y, x, drt);
                drt += 2;
                if (drt >= 4) {
                    drt -= 4;
                }
            }
            break;
        case 3:
            for (int i = 0; i < 2; i++) {
                watch(y, x, drt);
                drt += 1;
                if (drt >= 4) {
                    drt -= 4;
                }
            }
            break;
        case 4:
            for (int i = 0; i < 3; i++) {
                watch(y, x, drt);
                drt += 1;
                if (drt >= 4) {
                    drt -= 4;
                }
            }
            break;
        case 5:
            for (int i = 0; i < 4; i++) {
                watch(y, x, drt);
                drt += 1;
                if (drt >= 4) {
                    drt -= 4;
                }
            }
            break;
        }
    }

}

void watch(int y, int x, int drt) {
    int curY = y;
    int curX = x;
    while (1) {
        curY += dy[drt];
        curX += dx[drt];
        if (curY == -1 || curY == n || curX == -1 || curX == m || graph[curY][curX] == 6) {
            break;
        }
        else {
            graph[curY][curX] = 7;
        }
    }
}
void copyGraph() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            graph[i][j] = saved[i][j];
        }
    }
}

void getResult() {
    int temp = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (graph[i][j] == 0)
                temp++;
        }
    }
    result = min(result, temp);
}

후기 및 개선할 점

며칠을 걸려 풀었으며, 나만의 방식으로 풀었다는 것에 의의를 둔다.

You may also enjoy