15683번 감시

누가봐도 삼성 SW 역량 테스트 문제임을 알 수 있다.

BackTracking + Brute Force 문제이다.

나는 어떻게 접근 해야 하는지도 몰랐다. 

몇 시간 동안 계속 생각하다가, 다른 블로거 분의 정답 코드를 많이 참고하였다.

이런 문제 유형을 많이 연습해야겠다는 생각 뿐이다. 

더 열심히 노력해야겠다.

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

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int N = 0, M = 0;
 
int map[9][9] = { 0, };
 
int each_cctvCase[6] = { 0, 4, 2, 4, 4, 1 }; // 1 ~ 5 각각의 CCTV 경우의 수
 
vector<pair<int, int> > cctv; // cctv를 담을 vector
 
int ans = 987654321; // 답
 
void drawMap(int y, int x, int dy, int dx, int value)
{
    int row = y + dy;
    int column = x + dx;
 
    while (1 <= row && row <= N && 1 <= column && column <= M && map[row][column] != 6)
    {
        if (map[row][column] == 0 || map[row][column] >= 100)
        {
            map[row][column] += value;
        }
 
        row += dy;
        column += dx;
    }
}
 
void makeMap(int y, int x, int cctvnumber, int direction, int value)
{
    if (cctvnumber == 1)
    {
        if (direction == 1)
        {
            drawMap(y, x, 1, 0, value);
        }
        else if (direction == 2)
        {
            drawMap(y, x, 0, 1, value);
        }
        else if (direction == 3)
        {
            drawMap(y, x, -1, 0, value);
        }
        else if (direction == 4)
        {
            drawMap(y, x, 0, -1, value);
        }
    }
    else if (cctvnumber == 2)
    {
        if (direction == 1)
        {
            drawMap(y, x, 1, 0, value);
            drawMap(y, x, -1, 0, value);
        }
        else if (direction == 2)
        {
            drawMap(y, x, 0, 1, value);
            drawMap(y, x, 0, -1, value);
        }
    }
    else if (cctvnumber == 3)
    {
        if (direction == 1)
        {
            drawMap(y, x, -1, 0, value);
            drawMap(y, x, 0, 1, value);
        }
        else if (direction == 2)
        {
            drawMap(y, x, 0, 1, value);
            drawMap(y, x, 1, 0, value);
        }
        else if (direction == 3)
        {
            drawMap(y, x, 1, 0, value);
            drawMap(y, x, 0, -1, value);
        }
        else if (direction == 4)
        {
            drawMap(y, x, 0, -1, value);
            drawMap(y, x, -1, 0, value);
        }
    }
    else if (cctvnumber == 4)
    {
        if (direction == 1)
        {
            drawMap(y, x, 0, -1, value);
            drawMap(y, x, -1, 0, value);
            drawMap(y, x, 0, 1, value);
        }
        else if (direction == 2)
        {
            drawMap(y, x, -1, 0, value);
            drawMap(y, x, 0, 1, value);
            drawMap(y, x, 1, 0, value);
        }
        else if (direction == 3)
        {
            drawMap(y, x, 0, 1, value);
            drawMap(y, x, 1, 0, value);
            drawMap(y, x, 0, -1, value);
        }
        else if (direction == 4)
        {
            drawMap(y, x, 1, 0, value);
            drawMap(y, x, 0, -1, value);
            drawMap(y, x, -1, 0, value);
        }
    }
    else if (cctvnumber == 5)
    {
        drawMap(y, x, 1, 0, value);
        drawMap(y, x, 0, 1, value);
        drawMap(y, x, -1, 0, value);
        drawMap(y, x, 0, -1, value);
    }
}
 
int zeroCount()
{
    int ret = 0;
 
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            if (map[i][j] == 0)
            {
                ++ret;
            }
        }
    }
 
    return ret;
}
 
void get_Min(int start)
{
    if (start == cctv.size())
    {
        ans = min(ans, zeroCount()); // 사각 지대 최소 크기 구하기
 
        return;
    }
 
    int y = cctv[start].first;
    int x = cctv[start].second;
 
    int cctvNumber = map[y][x];
 
    for (int i = 1; i <= each_cctvCase[cctvNumber]; i++)
    {
        // BackTracking
 
        makeMap(y, x, cctvNumber, i, 100);
        get_Min(start + 1);
        makeMap(y, x, cctvNumber, i, -100); // map을 다시 원래대로 되돌리기 위함
    }
}
 
int main(void)
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            scanf("%d", &map[i][j]);
 
            if (1 <= map[i][j] && map[i][j] <= 5)
            {
                cctv.push_back({ i, j });
            }
        }
    }
    
    get_Min(0);
 
    printf("%d\n", ans);
 
    return 0;
}