[ 백준 15683 ] 감시 (C++) - 구현

---

🔗 문제 링크

15683번: 감시

---

💡 문제 풀이 및 해석

1. CCTV는 최대 8개이다. 모든 경우를 생각하면, 최악의 경우 (4번 CCTV가 64개 있을 때, 실제로는 3방향이니 24보다 많이 작다.)
   4^8 (모든 CCTV의 모든 방향 체크) \* 64 (맵의 복사) \* 24 (CCTV가 보는 방향 체크) = 100,663,296이다.
2. bruteforce한 방법으로 찾을 수 있다.
3. 나머지는 문제 조건 그대로 구현해주면 된다.

---

⭐️ 정답 코드 및 설명

#include<iostream>
#include<vector>
#define endl "\n"

using namespace std;

int N, M;
int answer;
vector<pair<int,int>> cctv;

void input(vector<vector<int>>& Map) {
    cin >> N >> M;
    answer = N * M;
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < M; x++) {
            int state; cin >> state;
            Map[y][x] = state;
            if (1 <= Map[y][x] && Map[y][x] <= 5) {
                cctv.push_back({ x,y });
            }
        }
    }
    cctv.push_back({ -1,-1 });
}

// CCTV Type에 따라서 sol()을 실행해야 하므로 위에 미리 선언함
void sol(int x, int y, int order, vector<vector<int>> Map);

// 바라보는 방향은 4방향임
void Up(int X, int Y, vector<vector<int>>& Map) {
    while (1) {
        if (Y - 1 < 0 || Map[Y - 1][X] == 6) break; // 범위를 벗어나거나 벽을 만나면 break
        if (Map[Y - 1][X] == 0) Map[Y - 1][X] = -1; // 볼 수 있는 곳 표기
        Y--;
    }
}
void Down(int X, int Y, vector<vector<int>>& Map) {
    while (1) {
        if (Y + 1 >= N || Map[Y + 1][X] == 6) break;
        if (Map[Y + 1][X] == 0) Map[Y + 1][X] = -1;
        Y++;
    }
}
void Left(int X, int Y, vector<vector<int>>& Map) {
    while (1) {
        if (X - 1 < 0 || Map[Y][X - 1] == 6) break;
        if (Map[Y][X - 1] == 0) Map[Y][X - 1] = -1;
        X--;
    }
}
void Right(int X, int Y, vector<vector<int>>& Map) {
    while (1) {
        if (X + 1 > M || Map[Y][X + 1] == 6) break;
        if (Map[Y][X + 1] == 0) Map[Y][X + 1] = -1;
        X++;
    }
}

// CCTV 타입별 구현
void Type1(int X, int Y, int dir, int order, vector<vector<int>> Map) {
    order++;
    int nx = cctv[order].first, ny = cctv[order].second;
    if (dir == 0) { // 위
        Up(X, Y, Map);
        sol(nx, ny, order, Map); // 다음 cctv 검사하러
    }
    if (dir == 1) { // 아래
        Down(X, Y, Map);
        sol(nx, ny, order, Map);
    }
    if (dir == 2) { // 왼쪽
        Left(X, Y, Map);
        sol(nx, ny, order, Map);
    }
    if (dir == 3) { // 오른쪽
        Right(X, Y, Map);
        sol(nx, ny, order, Map);
    }
}
void Type2(int X, int Y, int dir, int order, vector<vector<int>> Map) {
    order++;
    int nx = cctv[order].first, ny = cctv[order].second;
    int x = X, y = Y;
    if (dir == 0) { // 위 아래
        Up(X, Y, Map);
        Down(X, Y, Map);
        sol(nx, ny, order, Map);
    }
    if (dir == 1) { // 왼쪽 오른쪽
        Left(X, Y, Map);
        Right(X, Y, Map);
        sol(nx, ny, order, Map);
    }
}
void Type3(int X, int Y, int dir, int order, vector<vector<int>> Map) {
    order++;
    int nx = cctv[order].first, ny = cctv[order].second;
    int x = X, y = Y;
    if (dir == 0) { // 위 오른쪽
        Up(X, Y, Map);
        Right(X, Y, Map);
        sol(nx, ny, order, Map);
    }
    if (dir == 1) { // 위 왼쪽
        Up(X, Y, Map);
        Left(X, Y, Map);
        sol(nx, ny, order, Map);
    }
    if (dir == 2) { // 아래 오른쪽
        Down(X, Y, Map);
        Right(X, Y, Map);
        sol(nx, ny, order, Map);
    }
    if (dir == 3) { // 아래 왼쪽
        Down(X, Y, Map);
        Left(X, Y, Map);
        sol(nx, ny, order, Map);
    }
}
void Type4(int X, int Y, int dir, int order, vector<vector<int>> Map) {
    order++;
    int nx = cctv[order].first, ny = cctv[order].second;
    int x = X, y = Y;
    if (dir == 0) { // 아래 빼고
        Up(X, Y, Map);
        Left(X, Y, Map);
        Right(X, Y, Map);
        sol(nx, ny, order, Map);
    }
    if (dir == 1) { // 오른쪽 빼고
        Left(X, Y, Map);
        Up(X, Y, Map);
        Down(X, Y, Map);
        sol(nx, ny, order, Map);
    }
    if (dir == 2) { // 위 빼고
        Down(X, Y, Map);
        Right(X, Y, Map);
        Left(X, Y, Map);
        sol(nx, ny, order, Map);
    }
    if (dir == 3) { // 왼쪽 빼고
        Right(X, Y, Map);
        Up(X, Y, Map);
        Down(X, Y, Map);
        sol(nx, ny, order, Map);
    }
}
void Type5(int X, int Y, int order, vector<vector<int>> Map) {
    order++;
    int x = X, y = Y;
    int nx = cctv[order].first, ny = cctv[order].second;
    Up(X, Y, Map);
    Down(X, Y, Map);
    Left(X, Y, Map);
    Right(X, Y, Map);
    sol(nx, ny, order, Map);
}

// 구현된 CCTV Type으로 BruteForce하게 문제를 해결함
void sol(int x, int y, int order, vector<vector<int>> Map) { // cctv type, cctv order
    if (order >= cctv.size() - 1) {
        int Ans = 0;
        for (int y = 0; y < N; y++) {
            for (int x = 0; x < M; x++) {
                if (Map[y][x] == 0)  Ans++;
            }
        }
        answer = min(Ans, answer);
        return;
    }
    int type = Map[cctv[order].second][cctv[order].first];

    if (type == 1) {
        for (int dir = 0; dir < 4; dir++) {
            Type1(x, y, dir, order, Map);
        }
    }
    if (type == 2) {
        for (int dir = 0; dir < 2; dir++) {
            Type2(x, y, dir, order, Map);
        }
    }
    if (type == 3) {
        for (int dir = 0; dir < 4; dir++) {
            Type3(x, y, dir, order, Map);
        }
    }
    if (type == 4) {
        for (int dir = 0; dir < 4; dir++) {
            Type4(x, y, dir, order, Map);
        }
    }
    if (type == 5) {
        Type5(x, y, order, Map);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
    vector<vector<int>> Map(10, vector<int>(10, 6));
    input(Map);
    sol(cctv[0].first, cctv[0].second, 0, Map);
    cout << answer;
    return 0;
}

---

🤔 문제 후기

최근 푼 구현 문제 중에서는 실수를 가장 많이 했다.

(2번이나 틀렸다.)

CCTV가 볼 수 있는 상하좌우 함수를 따로 구현해주고, CCTV의 Type에 따라서 구현해주면 특별히 어려운 문제는 아니였는데, 처음에는 상하좌우를 따로 함수로 만들지 않고 직접 넣었는데, 이 때, X와 Y의 좌표를 매번 초기화 해줬어야 했는데, 해주지 않아서 생긴 문제와 nx와 ny를 넣어주는 부분에서 cctv의 index를 넘어가는 문제를 생각을 못했다. 여러가지 이유로 2번을 틀렸지만, 다시 생각하면 풀이를 생각하는 것은 어려운 문제가 아니였다. G4 구현 문제 중에서는 가장 어렵지 않았나 싶다.