[백준][삼성 SW역량 테스트] 15683. 감시

https://www.acmicpc.net/problem/15683

15683번: 감시

 

문제

위의 링크 참조

 

입력

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

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

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

 

출력

첫째 줄에 사각 지대의 최소 크기를 출력한다.

 

예제 입력1

4 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0

 

예제 출력1

20

 

생각

na 982 님의 강의를 듣고 풀었다.

 

1번 카메라의 경우 : 4방향

2번 카메라의 경우 : 2방향

3번 카메라의 경우 : 4방향

4번 카메라의 경우 : 4방향

5번 카메라의 경우 : 1방향

 

1. 시간 복잡도 계산하기

최악의 경우는 카메라가 총 8대 이기 때문에 4^8 = 65536 의 경우의 수가 발생하고,

매 경우마다 사무실의 최대 크기 8*8 에서 감시 못하는 공간을 카운트 하면 65536 * 64 = 약 400만

=> 가지치기를 잘 해줘야한다. 

 

2. 감시 카메라의 타입에 따라 회전가능한 방향의 크기를 미리 정의한다.

const int rot_size[] = { 4, 2, 4, 4, 1 };

 

작성한 코드

// 감시
#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
 
using namespace std;
 
struct CCTV
{
    int type, y, x;
};
 
int n, m, ans;
int map[8][8];
int cctv_size;
CCTV cctv[8];
 
const int rot_size[] = {4, 2, 4, 4, 1};
 
void map_copy(int desc[8][8], int src[8][8])
{
    for (int y = 0; y < n; y++)
    {
        for (int x = 0; x < m; x++)
        {
            desc[y][x] = src[y][x];
        }
    }
}
// dir =>  0(오) 1(위) 2(왼) 3(아)
void update(int dir, CCTV cctv)
{
    dir = (dir % 4);
 
    if (dir == 0)
    {
        for (int x = cctv.x + 1; x < m; x++)
        {
            if (map[cctv.y][x] == 6)
                break;
            map[cctv.y][x] = -1;
        }
    }
    if (dir == 1)
    {
        for (int y = cctv.y - 1; y >= 0; y--)
        {
            if (map[y][cctv.x] == 6)
                break;
            map[y][cctv.x] = -1;
        }
    }
    if (dir == 2)
    {
        for (int x = cctv.x - 1; x >= 0; x--)
        {
            if (map[cctv.y][x] == 6)
                break;
            map[cctv.y][x] = -1;
        }
    }
    if (dir == 3)
    {
        for (int y = cctv.y + 1; y < n; y++)
        {
            if (map[y][cctv.x] == 6)
                break;
            map[y][cctv.x] = -1;
        }
    }
}
void dfs(int cctv_index)
{
    if (cctv_index == cctv_size)
    {   
        // 사각지대 개수 구하기
        int cnt = 0;
        for (int y = 0; y < n; y++)
        {
            for (int x = 0; x < m; x++)
            {
                if (map[y][x] == 0)
                {
                    cnt++;
                }
            }
        }
        if (ans > cnt)
        {
            ans = cnt;
        }
 
        return;
    }
    int backup[8][8];
    int type = cctv[cctv_index].type;
    for (int dir = 0; dir < rot_size[type]; dir++)
    {
        // map 백업하기
        map_copy(backup, map);
        // map 업데이트
        if (type == 0)
        {
            update(dir, cctv[cctv_index]);
        }
        else if (type == 1)
        {
            update(dir, cctv[cctv_index]);
            update(dir + 2, cctv[cctv_index]);
        }
        else if (type == 2)
        {
            update(dir, cctv[cctv_index]);
            update(dir + 1, cctv[cctv_index]);
        }
        else if (type == 3)
        {
            update(dir, cctv[cctv_index]);
            update(dir + 1, cctv[cctv_index]);
            update(dir + 2, cctv[cctv_index]);
        }
        else if (type == 4)
        {
            update(dir, cctv[cctv_index]);
            update(dir + 1, cctv[cctv_index]);
            update(dir + 2, cctv[cctv_index]);
            update(dir + 3, cctv[cctv_index]);
        }
        dfs(cctv_index + 1);
        // map 원상복귀
        map_copy(map, backup);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
    for (int y = 0; y < n; y++)
    {
        for (int x = 0; x < m; y++)
        {
            cin >> map[y][x];
            
            if (map[y][x] != 0 && map[y][x] != 6)
            {
                cctv[cctv_size].y = y;
                cctv[cctv_size].x = x;
                cctv[cctv_size].type = map[y][x] - 1; // 0번부터 지정하기 위해서
                cctv_size++;
            }
        }
    }
 
    ans = 100;
    dfs(0);
 
    cout << ans << "\n";
    return 0;
}