[BOJ 15683] 감시 (C++)

감시(Gold 5)

문제

전체 문제 보기

15683번: 감시

 

접근법

문제에서 주어지는 카메라는 최대 8대입니다. 모든 카메라가 4방향으로 회전할 수 있다고 하더라도 \(4^8 = 65,536\)경우의 수가 존재하고 각 경우의 수마다 전체 맵(64칸)에 존재하는 사각지대를 카운트하면 되기 때문에 백트래킹을 활용한 완전 탐색을 하더라도 충분히 시간 내에 풀 수 있는 문제입니다. 다만 카메라의 회전을 구현하는 부분이 조금 복잡한 문제였습니다. 카메라의 회전은 다음과 같이 구현하였습니다.

구현

먼저 카메라가 현재 바라보는 방향을 아래와 같이 '-1'로 체크한다고 생각해볼 수 있습니다.

하지만, 카메라가 회전하게된다면 현재 바라보는 방향을 지워줘야 하는데 다음과 같은 문제가 발생할 수 있습니다.

위 그림처럼 1번 카메라가 바라보는 곳을 2번 카메라도 보고 있을 수 있습니다. 그런데 1번 카메라가 회전함에 따라서 2번 카메라가 바라보고 있는 공간이 삭제될 수도 있습니다. 이런 문제를 해결하기 위해서는 현재 바라보고 있는 방향을 다른 카메라도 바라보고 있는지 탐색하여 예외처리를 해야합니다.

 

탐색후 예외처리를 하는것 보다 더 간단한 방법으로 참조 카운터를 활용할 수 있습니다. 참조 카운터를 활용하는 것이 구현도 쉽고 불필요한 계산을 줄일 수 있습니다. 아래의 그림을 살펴봅시다.

위 그림처럼 지금 바라보는 방향의 값을 1씩 증가시킵니다. 그리고 회전하게된다면 바라보는 값을 1씩 감소시키고 새로운 방향을 다시 1 증가시킵니다.

정리하면 다음과 같은 순서로 진행할 수 있습니다.

• 지금 바라보는 방향의 값들을 1씩 감소
• 카메라 회전
• 지금 바라보는 방향의 값들을 1씩 증가

그리고 카메라가 바라보는 방향으로 값을 증가시키거나 감소시키기 위해서는 배열의 범위 검사와 벽에 대한 예외처리를 해야 합니다. 먼저 벽을 음수 값으로 설정하여 카메라가 바라보는 방향에서 음수가 나오기 전까지 배열의 값을 1씩 증가시키면 됩니다. 그리고 배열의 범위 검사를 하는대신 아래의 그림처럼 배열의 상하좌우에 음수값을 가진 패딩값을 만들어주면 별도의 범위검사를 하지 않아도 됩니다.

그리고 각 카메라가 바라보는 방향의 개수는 여러 개이기 때문에 dir을 동적 배열로 선언하여 타입에 맞게 방향을 설정할 수 있습니다. 이상 자세한 내용은 아래의 코드를 참조해 주세요.

전체 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define endl '\n'
using namespace std;

int N, M; //세로 크기 N과 가로 크기 M (1 ≤ N, M ≤ 8)
vector<vector<int>> map;
vector<struct Cam> cam;

//0:→ 1:↓ 2:← 3:↑
const int dr[4] = { 0, 1, 0, -1 };
const int dc[4] = { 1, 0, -1, 0 };

struct Pos {
    Pos() {}
    Pos(int _r, int _c) : r{ _r }, c{ _c } {}
    int r{};
    int c{};
};
class Cam {
public:
    Cam(Pos _pos, int _t);
    void Rotate(); // 카메라 회전
    void Init();   // 맵에 카메라 설치(초기화)
    int GetRCnt() { return rCnt; }
private:
    Pos pos;
    int t;
    int rCnt;
    vector<int> dir;
    void view(); // dir 방향으로 체킹
    void clear(); // dir 방향으로 체킹 해제 
};
Cam::Cam(Pos _pos, int _t) : pos{ _pos }, t{ _t }, dir{}
{
    if (_t == 1)
    {
        rCnt = 3;
        dir.push_back(0); // 0:→
    }
    else if (_t == 2)
    {
        rCnt = 1;
        dir.push_back(0); // 0:→
        dir.push_back(2); // 2:←
    }
    else if (_t == 3)
    {
        rCnt = 3;
        dir.push_back(0); // 0:→
        dir.push_back(3); // 3:↑
    }                        
    else if (_t == 4)        
    {                        
        rCnt = 3;            
        dir.push_back(0); // 0:→
        dir.push_back(2); // 2:←
        dir.push_back(3); // 3:↑
    }
    else
    {
        rCnt = 0;
        dir.push_back(0); // 0:→
        dir.push_back(1); // 1:↓
        dir.push_back(2); // 2:← 
        dir.push_back(3); // 3:↑ 
    }
}
void Cam::Rotate()
{
    clear();
    for (int& d : dir)
    {
        d++;
        d %= 4;
    }
    view();
}
void Cam::Init()
{
    view();
}
void Cam::view()
{
    for (int i : dir)
    {
        Pos next{ pos.r + dr[i], pos.c + dc[i] };
        while (map[next.r][next.c] >= 0)
        {
            map[next.r][next.c]++;
            next.r += dr[i];
            next.c += dc[i];
        }
    }
}
void Cam::clear()
{
    for (int i : dir)
    {
        Pos next{ pos.r + dr[i], pos.c + dc[i] };
        while (map[next.r][next.c] >= 0)
        {
            map[next.r][next.c]--;
            next.r += dr[i];
            next.c += dc[i];
        }
    }
}
void PrintMap()
{
    for (int i = 0; i < N + 2; ++i)
    {
        for (int j = 0; j < M + 2; ++j)
        {
            cout << setw(2) <<map[i][j] << " ";
        }
        cout << endl;
    }
}

int EmptyCnt()
{
    int retval{};
    for (int i = 1; i < N + 1; ++i)
    {
        for (int j = 1; j < M + 1; ++j)
        {
            if (map[i][j] == 0)
                retval++;
        }
    }
    //cout << retval << "▼" << endl;
    //PrintMap();
    //cout << endl;
    return retval;
}

int BT(int idx)
{
    if (idx == cam.size())
        return EmptyCnt();
    
    int rCnt = cam[idx].GetRCnt();
    // 초기 방향으로 탐색
    int retval = BT(idx + 1);
    // 회전가능하다면 회전 후 탐색
    for (int i = 0; i < rCnt; ++i)
    {
        cam[idx].Rotate();
        retval = min(retval, BT(idx + 1));
    }
    return retval;
}

int main()
{
    //입출력 성능향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    cin >> N >> M;
    map.resize(N + 2);
    map[0].resize(M + 2, -9);
    map[N + 1].resize(M + 2, -9);

    for (int i = 1; i < N + 1; ++i)
    {
        map[i].resize(M + 2 , -9);
        for (int j = 1; j < M + 1; ++j)
        {
            cin >> map[i][j];
            if (map[i][j] == 6)
                map[i][j] = -9;
            else if (map[i][j] != 0)
            {
                cam.emplace_back(Pos(i, j), map[i][j]);
                map[i][j] += 10;
            }
        }
    }
    for (auto& c : cam)
    {
        c.Init();
    }
    cout << BT(0);

    return 0;
}