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

15683번 : 감시

---

문제)

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.

 

 

1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.

CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.

CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0

지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호이다. 위의 예시에서 1번의 방향에 따라 감시할 수 있는 영역을 '#'로 나타내면 아래와 같다.

CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 칸을 감시할 수 없다.

0 0 0 0 0 0
0 2 0 0 0 0
0 0 0 0 6 0
0 6 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 5

위의 예시에서 감시할 수 있는 방향을 알아보면 아래와 같다.

CCTV는 CCTV를 통과할 수 있다. 아래 예시를 보자.

0 0 2 0 3
0 6 0 0 0
0 0 6 6 0
0 0 0 0 0

위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.

# # 2 # 3
0 6 # 0 #
0 0 6 6 #
0 0 0 0 #

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

 

 

입력 :

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

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

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

 

 

 

출력 :

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

 

 

 

 

풀이)

오랜만에 정말 무자비한 하드코딩을 한 것 같다.

 

// 15683. 감시
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, m;
vector<vector<int>> vec;
int node_cnt;
vector<pair<int, int>> node;
 
int ans = 99999999;
void check(int a, int b, int drt, vector<vector<int>>& temp)
{
    if (0 > a || a >= n) return;
    if (0 > b || b >= m) return;
    if (temp[a][b] == 6) return;
 
    if (temp[a][b] == 0)
    {
        temp[a][b] = 7;
    }
 
    if (drt == 0)        // 상
    {
        check(a - 1, b, drt, temp);
    }
    else if (drt == 1)    // 좌
    {
        check(a, b - 1, drt, temp);
    }
    else if (drt == 2)    // 하
    {
        check(a + 1, b, drt, temp);
    }
    else if (drt == 3)    // 우
    {
        check(a, b + 1, drt, temp);
    }
}
 
void recur(int cur, vector<vector<int>> t)
{
    if (cur == node_cnt)
    {
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (t[i][j] == 0)
                {
                    cnt++;
                }
            }
        }
 
        ans = min(ans, cnt);
        return;
    }
 
    int x = node[cur].first;
    int y = node[cur].second;
    if(t[x][y] == 1)
    {
        for (int i = 0; i < 4; i++)
        {
            vector<vector<int>> temp;
            temp = t;
            check(x, y, i, temp);
            recur(cur + 1, temp);
        }
    }
    else if (t[x][y] == 2)
    {
        vector<vector<int>> temp;
        temp = t;
        check(x, y, 0, temp);
        check(x, y, 2, temp);
        recur(cur + 1, temp);
 
        temp = t;
        check(x, y, 1, temp);
        check(x, y, 3, temp);
        recur(cur + 1, temp);
    }
    else if (t[x][y] == 3)
    {
        vector<vector<int>> temp;
        temp = t;
        check(x, y, 0, temp);
        check(x, y, 1, temp);
        recur(cur + 1, temp);
 
        temp = t;
        check(x, y, 1, temp);
        check(x, y, 2, temp);
        recur(cur + 1, temp);
 
        temp = t;
        check(x, y, 2, temp);
        check(x, y, 3, temp);
        recur(cur + 1, temp);
 
        temp = t;
        check(x, y, 3, temp);
        check(x, y, 0, temp);
        recur(cur + 1, temp);
    }
    else if (t[x][y] == 4)
    {
        vector<vector<int>> temp;
        temp = t;
        check(x, y, 1, temp);
        check(x, y, 2, temp);
        check(x, y, 3, temp);
        recur(cur + 1, temp);
 
        temp = t;
        check(x, y, 2, temp);
        check(x, y, 3, temp);
        check(x, y, 0, temp);
        recur(cur + 1, temp);
 
        temp = t;
        check(x, y, 0, temp);
        check(x, y, 1, temp);
        check(x, y, 3, temp);
        recur(cur + 1, temp);
 
        temp = t;
        check(x, y, 0, temp);
        check(x, y, 1, temp);
        check(x, y, 2, temp);
        recur(cur + 1, temp);
    }
    else if (t[x][y] == 5)
    {
        vector<vector<int>> temp;
        temp = t;
        check(x, y, 0, temp);
        check(x, y, 1, temp);
        check(x, y, 2, temp);
        check(x, y, 3, temp);
        recur(cur + 1, temp);
    }
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
    vec.resize(n, vector<int>(m, 0));
 
    int cnt = 0;
    int temp;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> temp;
            vec[i][j] = temp;
            if (temp > 0 && temp < 6)
            {
                node.push_back(make_pair(i, j));
                node_cnt++;
            }
        }
    }
 
    recur(0, vec);
 
    cout << ans;
 
    return 0;
}
 

---

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

15683번: 감시