[C++] 백준 15683번: 감시

🔗 문제

15683번: 감시

15683번: 감시

첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.

CCTV의 최대 개수는 8개를 넘지 않는다.

 

🖍 풀이

 

문제를 보면 맵도 작고 CCTV 개수도 작기 떄문에 완전 탐색으로 풀어주었다.

소스를 보는게 빠를 듯하지만 설명을 해볼게요..

1. 현재 map 상태를 copied에 저장한다.
2. CCTV 타입에 방향에 맞게 사각지대를 밝힌다. (위치를 -1로 변경)
3. CCTV 개수만큼의 재귀함수가 호출된다.
4. 모든 CCTV가 사각지대를 밝힌 후, 남은 사각지대 개수를 센다. (counting) 이후 재귀함수 리턴.
5. 마지막으로 호출된 CCTV부터 다음 방향으로 비춰야한다. (d에 대한 반복문)
   1. 이때, CCTV 방향을 바꾸기 위해 원래 상태가 필요하다 → 과정 1에서 저장한 copied 값을 map에 저장해 복구

과정 1~5로 모든 경우를 싹싹 뒤져 정답을 찾을 수 있다.

 

 

CCTV 타입마다 여러 방향을 보는 방법은 아래의 solve() 함수를 참고하세요. 

비춰야할 방향의 개수는 monitoring() 개수로, 방향은 monitoring()의 매개변수 d를 이용해 아래 방법으로 잘 방향을 돌려줬습니다. 

    if(d >= 4)
        d = (d%4); // 0, 1, 2 || 1, 2, 3 || 2, 3, 0 < 이렇게 방향 순환 시키기

void solve(int idx)
{
    if(idx == CCTV.size()) // 모든 CCTV를 비췄으면
    {
        int tmp = counting(); // 사각지대의 개수를 센다.
        answer = (answer < tmp ? answer : tmp);
        return ;
    }
    
    int temp[MAX][MAX];
    
    if(CCTV[idx].type == 1)
    {
        for(int d=0; d<4; ++d)
        {
            copy_map(map, temp); // CCTV 비추기 전 상태를 저장한다.

            monitoring(CCTV[idx].x, CCTV[idx].y, d); // d 방향에 따라 CCTV를 비춘다.
            solve(idx+1); // 다음 CCTV를 비춘다. 

            copy_map(temp, map); // CCTV 각도를 바꾸기 위해 현재 CCTV 비추기 전으로 돌아간다.
            
            ///...... 생략 타입마다 monitoring 호출 횟수가 다르다..!!
    }

}

 

💾  소스

#include <iostream>

const int MAX  = 9;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};

int answer = 9*9;
int N, M;
int map[MAX][MAX];

struct info
{
    info() = default;
    info(const int x, const int y, const int type)
    :x(x), y(y), type(type) {}
    
    int x, y;
    int type;
};
std::vector<info> CCTV;

void show(const int (*arr)[MAX])
{
    std::cout << "===show===\\n";
    for(int i=0; i<N; ++i)
    {
        for(int j=0; j<M; ++j)
        {
            std::cout << arr[i][j] << ' ';
        }
        std::cout << '\\n';
    }
}

bool isValid(const int x, const int y)
{
    if(x<0 || y<0 || x>=N || y>=M)
        return false;
    return true;
}

void monitoring(int x, int y, int d, int state = -1)
{
    if(d >= 4)
        d = (d%4); // 0, 1, 2 || 1, 2, 3 || 2, 3, 0 < 이렇게 방향 순환 시키기

    // -1 감시 중
    // 0 사각지대
    while(1)
    {
        x += dx[d];
        y += dy[d];
        
        if(!isValid(x, y) || map[x][y] == 6)
            break;
        
        if(map[x][y] == 0)
            map[x][y] = state;
    }
}

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

void  copy_map(int (*origin)[MAX], int (*copied)[MAX])
{
    for(int i=0; i<N; ++i)
    {
        for(int j=0; j<M; ++j)
        {
            copied[i][j] = origin[i][j];
        }
    }
}

void solve(int idx)
{
    if(idx == CCTV.size())
    {
        int tmp = counting();
        answer = (answer < tmp ? answer : tmp);
        return ;
    }
    
    int temp[MAX][MAX];
    
    if(CCTV[idx].type == 1)
    {
        for(int d=0; d<4; ++d)
        {
            copy_map(map, temp);
            
            monitoring(CCTV[idx].x, CCTV[idx].y, d);
            solve(idx+1);
            
            copy_map(temp, map);

        }
    }
    else if(CCTV[idx].type == 2)
    {
        for(int d=0; d<2; ++d)
        {
            copy_map(map, temp);

            monitoring(CCTV[idx].x, CCTV[idx].y, d);
            monitoring(CCTV[idx].x, CCTV[idx].y, d+2);
            solve(idx+1);
            
            copy_map(temp, map);
        }
    }
    else if(CCTV[idx].type == 3)
    {
        for(int d=0; d<4; ++d)
        {
            copy_map(map, temp);

            monitoring(CCTV[idx].x, CCTV[idx].y, d);
            monitoring(CCTV[idx].x, CCTV[idx].y, d+1);
            solve(idx+1);
            
            copy_map(temp, map);

        }
    }
    else if(CCTV[idx].type == 4)
    {
        for(int d=0; d<4; ++d)
        {
            copy_map(map, temp);

            monitoring(CCTV[idx].x, CCTV[idx].y, d);
            monitoring(CCTV[idx].x, CCTV[idx].y, d+1);
            monitoring(CCTV[idx].x, CCTV[idx].y, d+2);
            solve(idx+1);
            
            copy_map(temp, map);

        }
    }
    else if(CCTV[idx].type == 5)
    {
        for(int d=0; d<4; ++d)
        {
            copy_map(map, temp);

            monitoring(CCTV[idx].x, CCTV[idx].y, d);
            monitoring(CCTV[idx].x, CCTV[idx].y, d+1);
            monitoring(CCTV[idx].x, CCTV[idx].y, d+2);
            monitoring(CCTV[idx].x, CCTV[idx].y, d+3);
            solve(idx+1);
            
            copy_map(temp, map);
        }
    }

}

int main()
{
    std::cin >> N >> M;
    for(int i=0; i<N; ++i)
    {
        for(int j=0; j<M; ++j)
        {
            std::cin >> map[i][j];
            if(map[i][j] > 0 && map[i][j] != 6)
                CCTV.push_back({i, j, map[i][j]});
        }
    }
    
    solve(0);
   
    std::cout << answer;
    
    return 0;
}