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

26 Mar 2024 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 입력
• 출력
• 알고리즘
• 풀이
• 코드
• 평가

문제

BOJ - 15683 : 감시(링크)

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

입력

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

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

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

출력

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

알고리즘

풀이

코드

// BOJ-15683 : 감시
#include <bits/stdc++.h>
using namespace std;

const int INF = 2147000000;
const int dy[] = { -1,0,1,0 };
const int dx[] = { 0,1,0,-1 };

int n, m, a[10][10], visited[10][10], dir, res = INF;

vector<pair<int, int>> v;

vector<pair<int, int>> extendCCTV(int here, int dir)
{
	vector<pair<int, int>> _change;
	int y = v[here].first;
	int x = v[here].second;

	if (a[y][x] == 1)
	{
		while (true)
		{
			int ny = y + dy[dir];
			int nx = x + dx[dir];

			if (ny < 0 || nx < 0 || ny >= n || nx >= m || a[ny][nx] == 6) break;

			if (a[ny][nx] == 0)
			{
				a[ny][nx] = 8;
				_change.push_back({ ny,nx });
			}
			y = ny;
			x = nx;
		}
	}
	else if (a[y][x] == 2)
	{
		for (int i = 0; i <= 2; i += 2)
		{
			int _y = y;
			int _x = x;
			while (true)
			{
				int ny = _y + dy[(dir + i) % 4];
				int nx = _x + dx[(dir + i) % 4];

				if (ny < 0 || nx < 0 || ny >= n || nx >= m || a[ny][nx] == 6) break;
				
				if (a[ny][nx] == 0)
				{
					a[ny][nx] = 8;
					_change.push_back({ ny,nx });
				}
				_y = ny;
				_x = nx;
			}

		}
	}
	else if (a[y][x] == 3)
	{
		for (int i = 0; i < 2; i++)
		{
			int _y = y;
			int _x = x;
			while (true)
			{
				int ny = _y + dy[(dir + i) % 4];
				int nx = _x + dx[(dir + i) % 4];

				if (ny < 0 || nx < 0 || ny >= n || nx >= m || a[ny][nx] == 6) break;
				
				if (a[ny][nx] == 0)
				{
					a[ny][nx] = 8;
					_change.push_back({ ny,nx });
				}
				_y = ny;
				_x = nx;
			}
		}
	}
	else if (a[y][x] == 4)
	{
		for (int i = 0; i < 3; i++)
		{
			int _y = y;
			int _x = x;
			while (true)
			{
				int ny = _y + dy[(dir + i) % 4];
				int nx = _x + dx[(dir + i) % 4];

				if (ny < 0 || nx < 0 || ny >= n || nx >= m || a[ny][nx] == 6) break;

				if (a[ny][nx] == 0)
				{
					a[ny][nx] = 8;
					_change.push_back({ ny,nx });
				}
				_y = ny;
				_x = nx;
			}
		}
	}
	else if (a[y][x] == 5)
	{
		for (int i = 0; i < 4; i++)
		{
			int _y = y;
			int _x = x;

			while (true)
			{
				int ny = _y + dy[(dir + i) % 4];
				int nx = _x + dx[(dir + i) % 4];

				if (ny < 0 || nx < 0 || ny >= n || nx >= m || a[ny][nx] == 6) break;

				if (a[ny][nx] == 0)
				{
					a[ny][nx] = 8;
					_change.push_back({ ny,nx });
				}
				_y = ny;
				_x = nx;
			}
		}
	}
	return _change;
}

void dfs(int here)
{
	// 종료조건
	if (here == v.size())
	{
		int cnt = 0;

		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (a[i][j] == 0)
				{
					cnt++;
				}
			}
		}

		res = min(res, cnt);
		return;
	}

	// 네 방향 완전 탐색
	for (int i = 0; i < 4; i++)
	{
		vector<pair<int, int>> _change = extendCCTV(here, i);
		dfs(here + 1);
		for (auto b : _change) a[b.first][b.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 });
			}
		}
	}

	dfs(0);

	cout << res << '\n';

	return 0;
}

평가

-