백준 15683 감시 C++

문제

www.acmicpc.net/problem/15683

15683번: 감시

코드

#include<bits/stdc++.h>

using namespace std;
int n, m, ret = 987654321, a[10][10], visited[10][10];
int dy[4] = { -1, 0, 1, 0 }, dx[4] = { 0, 1, 0, -1 };
vector<pair<int, int>> v;

void getCCTVPositionList(int y, int x, int cctvDir, int num, vector<pair<int, int>>& tempCCTVPosition)
{
    while (true)
    {
        int ny = y + dy[(cctvDir + num) % 4];
        int nx = x + dx[(cctvDir + num) % 4];
        if (ny >= 0 && ny < n && nx >= 0 && nx < m && a[ny][nx] != 6)
        {
            if (a[ny][nx] == 0)
            {
                a[ny][nx] = 8;
                tempCCTVPosition.push_back({ ny, nx });
            }
            y = ny;
            x = nx;
        }
        else
        {
            break;
        }
    }
}


vector<pair<int, int>> monitoringCCTVRegion(int cctvCount, int cctvDir)
{
    vector<pair<int, int>> tempCCTVPosition;
    int y = v[cctvCount].first;
    int x = v[cctvCount].second;

    if (a[y][x] == 1)
    {
        getCCTVPositionList(y, x, cctvDir, 0, tempCCTVPosition);
    }
    else if (a[y][x] == 2)
    {
        for (int i = 0; i <= 2; i += 2)
        {
            getCCTVPositionList(y, x, cctvDir, i, tempCCTVPosition);
        }
    }
    else if (a[y][x] == 3)
    {
        for (int i = 0; i < 2; i ++)
        {
            getCCTVPositionList(y, x, cctvDir, i, tempCCTVPosition);
        }
    }
    else if (a[y][x] == 4)
    {
        for (int i = 0; i < 3; i++)
        {
            getCCTVPositionList(y, x, cctvDir, i, tempCCTVPosition);
        }
    }
    else if (a[y][x] == 5)
    {
        for (int i = 0; i < 4; i++)
        {
            getCCTVPositionList(y, x, cctvDir, i, tempCCTVPosition);
        }
    }

    return tempCCTVPosition;
}

void go(int cctvCount)
{  
    //기저사례
    if (cctvCount == v.size())
    {
        //사각지대 영역 Count
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (a[i][j] == 0)
                    cnt++;
            }
        }
        ret = min(cnt, ret);
        return;
    }

    for (int i = 0; i < 4; i++)
    {
        vector<pair<int, int>> monitoringCCTVRegionList = monitoringCCTVRegion(cctvCount, i);
        go(cctvCount + 1);
        for (auto cctvPosition : monitoringCCTVRegionList)
        {
            a[cctvPosition.first][cctvPosition.second] = 0;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
     
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> a[i][j];
            if (a[i][j] != 0 && a[i][j] != 6)
            {
                v.push_back({ i,j });
            }
        }
    }

    go(0);

    cout << ret << "\n";

    return 0;
}