kunkunwoo@blog:~$ 거누권의 생각깜지

백준 15683번_ 감시

· 배운 것 · 10분 읽기

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

15683번: 감시

풀이방법

1. cctv를 기준으로 left, right, up, down을 채울수 있는 함수 4개를 만든다. (밑의 코드참조)

void fillup(pair<int, int>pos, vector<vector<int>>& calmap)
{
	while (1)
	{
		pos.first -= 1;
		if (pos.first < 0)
			break;
		
		if (calmap[pos.first][pos.second] == 0)
			calmap[pos.first][pos.second] = 7;
		else if (calmap[pos.first][pos.second] == 6)
			break;
	}
}
//... 나머지 down, left, right도 이런식으로 만들면 된다.

2. dfs를 이용해서 방향 선택의 모든 경우의 수를 모두 돌리고 빈 공간을 계산한다.

ex) cctv1이면 상, 하, 좌, 우로 4가지 경우가 나올수 있음, cctv2이면 상하, 좌우로 2가지 경우가 나올수 있음 ....

전체코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits.h>

using namespace std;

class cctvInformation
{
public:
	int y;
	int x;
	int cctvtype;

	cctvInformation(int y_in, int x_in, int cctvtype_in)
		:y(y_in), x(x_in), cctvtype(cctvtype_in)
	{}
};

int n, m;
vector<vector<int>> map;
vector<cctvInformation> cctv;

void fillup(pair<int, int>pos, vector<vector<int>>& calmap)
{
	while (1)
	{
		pos.first -= 1;
		if (pos.first < 0)
			break;
		
		if (calmap[pos.first][pos.second] == 0)
			calmap[pos.first][pos.second] = 7;
		else if (calmap[pos.first][pos.second] == 6)
			break;
	}
}

void filldown(pair<int, int>pos, vector<vector<int>>& calmap)
{
	while (1)
	{
		pos.first += 1;
		if (pos.first >= n)
			break;

		if (calmap[pos.first][pos.second] == 0)
			calmap[pos.first][pos.second] = 7;
		else if (calmap[pos.first][pos.second] == 6)
			break;
	}
}

void fillleft(pair<int, int>pos, vector<vector<int>>& calmap)
{
	while (1)
	{
		pos.second -= 1;
		if (pos.second < 0)
			break;

		if (calmap[pos.first][pos.second] == 0)
			calmap[pos.first][pos.second] = 7;
		else if (calmap[pos.first][pos.second] == 6)
			break;
	}
}

void fillright(pair<int, int>pos, vector<vector<int>>& calmap)
{
	while (1)
	{
		pos.second += 1;
		if (pos.second >= m)
			break;

		if (calmap[pos.first][pos.second] == 0)
			calmap[pos.first][pos.second] = 7;
		else if (calmap[pos.first][pos.second] == 6)
			break;
	}
}

int minValue = INT_MAX;
int getEmptyPlace(vector<vector<int>> calmap)
{
	int cnt = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (calmap[i][j] == 0)
				cnt++;

	return cnt;
}

void dfs(vector<vector<int>>calmap, int cnt)
{
	if (cnt == cctv.size())
	{
		//check
		minValue = min(minValue, getEmptyPlace(calmap));
		return;
	}

	//check cctvtype
	int cctvtype = cctv[cnt].cctvtype;
	pair<int, int>pos = { cctv[cnt].y, cctv[cnt].x };

	//cctvtype에 따라 다르게 dfs보냄
	if (cctvtype == 1)
	{
		vector<vector<int>>nextcalmap = calmap;

		//1은 4가지경우가 있음
		fillup(pos, nextcalmap);
		dfs(nextcalmap, cnt + 1);

		nextcalmap = calmap;
		filldown(pos, nextcalmap);
		dfs(nextcalmap, cnt + 1);

		nextcalmap = calmap;
		fillleft(pos, nextcalmap);
		dfs(nextcalmap, cnt + 1);

		nextcalmap = calmap;
		fillright(pos, nextcalmap);
		dfs(nextcalmap, cnt + 1);

	}

	else if (cctvtype == 2)
	{
		vector<vector<int>>nextcalmap = calmap;

		//2은 2가지경우가 있음
		fillup(pos, nextcalmap);
		filldown(pos, nextcalmap);
		dfs(nextcalmap, cnt + 1);

		nextcalmap = calmap;
		fillleft(pos, nextcalmap);
		fillright(pos, nextcalmap);
		dfs(nextcalmap, cnt + 1);
	}

	else if (cctvtype == 3)
	{
		vector<vector<int>>nextcalmap = calmap;

		//3은 4가지경우가 있음
		fillup(pos, nextcalmap);
		fillleft(pos, nextcalmap);
		dfs(nextcalmap, cnt + 1);

		nextcalmap = calmap;
		filldown(pos, nextcalmap);
		fillleft(pos, nextcalmap);
		dfs(nextcalmap, cnt + 1);

		nextcalmap = calmap;
		filldown(pos, nextcalmap);
		fillright(pos, nextcalmap);
		dfs(nextcalmap, cnt + 1);

		nextcalmap = calmap;
		fillright(pos, nextcalmap);
		fillup(pos, nextcalmap);
		dfs(nextcalmap, cnt + 1);
	}

	else if (cctvtype == 4)
	{
		vector<vector<int>>nextcalmap = calmap;

		//4은 4가지경우가 있음
		fillup(pos, nextcalmap);
		fillleft(pos, nextcalmap);
		fillright(pos, nextcalmap);
		dfs(nextcalmap, cnt + 1);

		nextcalmap = calmap;
		filldown(pos, nextcalmap);
		fillleft(pos, nextcalmap);
		fillup(pos, nextcalmap);
		dfs(nextcalmap, cnt + 1);

		nextcalmap = calmap;
		fillleft(pos, nextcalmap);
		filldown(pos, nextcalmap);
		fillright(pos, nextcalmap);
		dfs(nextcalmap, cnt + 1);

		nextcalmap = calmap;
		fillright(pos, nextcalmap);
		fillup(pos, nextcalmap);
		filldown(pos, nextcalmap);
		dfs(nextcalmap, cnt + 1);
	}

	else if (cctvtype == 5)
	{
		vector<vector<int>>nextcalmap = calmap;

		//5은 1가지경우가 있음
		fillup(pos, nextcalmap);
		fillleft(pos, nextcalmap);
		fillright(pos, nextcalmap);
		filldown(pos, nextcalmap);
		dfs(nextcalmap, cnt + 1);
	}
}


int main()
{
	map.resize(9);
	for (int i = 0; i < 8; i++)
		map[i].resize(9);

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		int value;
		for (int j = 0; j < m; j++)
		{
			cin >>  value;
			map[i][j] = value;

			//cctv 위치, 타입 저장
			if (value != 0 && value != 6)
			{
				cctv.push_back(cctvInformation(i, j, value));
			}
		}
	}

	dfs(map, 0);

	cout << minValue;

	return 0;
}

후기

함수를 배열화 시켜서 dfs를 반복문을 통해 간단하게 다시 짜서 올리고 싶었는데 짜다가 너무 귀찮아져서 그냥 예전에 하드코딩했던 코드를 올린다. 이렇게 짜지말고 dir[] = {{u,d,l,r}, {ud, lr}....} 이런식으로 짤것.