백준/15683번/감시/골드4

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

문제 설명

Site: Baekjoon
Number: 15683
Category: Bruteforce, Backtracking
Rank: Gold 4

브루트포스 문제여서 그런가 코드의 양이 조금 많은 문제였다.

주어진 N x M 크기의 배열에서 5가지 종류의 CCTV에 따라 감시할 수 있는 모든 경우의 수를 파악하고 이 때 가장 적게 나오는 사각지대 수를 구하는 문제이다.

입력 받은 배열에서 CCTV의 위치와 종류를 tuple배열에 저장하고, 각 CCTV마다 90도씩 돌려가며 범위를 검사하는 방식을 사용하였다.

함수 별 기능
BlindSpot: 현재 배열에서 사각지대의 갯수를 찾아 return하는 함수.
Line: 주어진 방향으로 벽이 나올때까지 CCTV가 탐지한 지역으로 변환하여 사각지대를 없애는 함수.
View: 주어진 CCTV에 따라 확인하는 방향을 Line을 통해 표시한다. Check: 각 CCTV마다 90도씩 4번 돌려가며 모든 경우의 수를 확인하고, 모든 CCTV를 체크한 경우 사각지대 최솟값을 갱신하는 함수.

#include <iostream>
#include <tuple>
#include <vector>

#define TIII tuple<int, int, int>

using namespace std;

int N, M, ans = 64;

vector<TIII> v;

enum
{
	LEFT, UP, RIGHT, DOWN
};

int BlindSpot(vector<vector<int>> office)
{
    int cnt = 0;
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < M; j++)
		{
            if (office[i][j] == 0)
                cnt++;
		}
	}

    return cnt;
}

void Line(int x, int y, int dir, vector<vector<int>>& office)
{

	switch(dir)
	{
	case LEFT:
		y--;
		while(x < N && y < M && x > -1 && y > -1 && office[x][y] != 6)
		{
			if (office[x][y] == 0)
				office[x][y] = 7;

			y--;
		}
		break;

	case UP:
		x--;
		while (x < N && y < M && x > -1 && y > -1 && office[x][y] != 6)
		{
			if (office[x][y] == 0)
				office[x][y] = 7;

			x--;
		}
		break;

	case RIGHT:
		y++;
		while (x < N && y < M && x > -1 && y > -1 && office[x][y] != 6)
		{
			if (office[x][y] == 0)
				office[x][y] = 7;

			y++;
		}
		break;

	case DOWN:
		x++;
		while (x < N && y < M && x > -1 && y > -1 && office[x][y] != 6)
		{
			if (office[x][y] == 0)
				office[x][y] = 7;

			x++;
		}
		break;
	}
}

vector<vector<int>> View(TIII camera, vector<vector<int>> office, int i)
{
    int x = get<0>(camera);
    int y = get<1>(camera);
	switch(get<2>(camera))
	{
	case 1:
		Line(x, y, i, office);
		break;
	case 2:
		Line(x, y, i, office);
		Line(x, y, (i + 2) % 4, office);
		break;
	case 3:
		Line(x, y, i, office);
		Line(x, y, (i + 1) % 4, office);
		break;
	case 4:
		Line(x, y, i, office);
		Line(x, y, (i + 1) % 4, office);
		Line(x, y, (i + 2) % 4, office);
		break;
	case 5:
		Line(x, y, 0, office);
		Line(x, y, 1, office);
		Line(x, y, 2, office);
		Line(x, y, 3, office);
		break;
	}
	return office;
}

void Check(int cnt, vector<vector<int>> office)
{
	if(cnt == v.size())
	{
        ans = min(ans, BlindSpot(office));
        return;
	}

    for(int i = 0; i < 4; i++)
    {
        vector<vector<int>> off = View(v[cnt], office, i);
        Check(cnt+1, off);
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> N >> M;

    vector<vector<int>> office(N, vector<int>(M, 0));
    for(int i = 0; i < N; i++)
    {
	    for(int j = 0; j < M; j++)
	    {
            cin >> office[i][j];
            if(office[i][j] != 0 && office[i][j] != 6)
            {
                v.emplace_back(i, j, office[i][j]);
            }
	    }
    }

	Check(0, office);

	cout << ans;
}