- 문제
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.
1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.
CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.
CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호이다. 위의 예시에서 1번의 방향에 따라 감시할 수 있는 영역을 '#'로 나타내면 아래와 같다.
CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 칸을 감시할 수 없다.
0 0 0 0 0 0
0 2 0 0 0 0
0 0 0 0 6 0
0 6 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 5위의 예시에서 감시할 수 있는 방향을 알아보면 아래와 같다.
CCTV는 CCTV를 통과할 수 있다. 아래 예시를 보자.
0 0 2 0 3
0 6 0 0 0
0 0 6 6 0
0 0 0 0 0
위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.
# # 2 # 3
0 6 # 0 #
0 0 6 6 #
0 0 0 0 #
사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.
- 입력
첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.
CCTV의 최대 개수는 8개를 넘지 않는다.
- 출력
첫째 줄에 사각 지대의 최소 크기를 출력한다.
- 예제 입력
4 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 06 6
0 0 0 0 0 0
0 2 0 0 0 0
0 0 0 0 6 0
0 6 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 56 6
1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 16 6
1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 5 0 0
0 0 5 1 0 0
0 0 0 0 1 0
0 0 0 0 0 11 7
0 1 2 3 4 5 63 7
4 0 0 0 0 0 0
0 0 0 2 0 0 0
0 0 0 0 0 0 4- 예제 출력
20156200- 접근방식
CCTV마다 탐색 범위를 다르게 설정해서 해당 좌표들을 변경한다음에
dfs를 통해 사각지대를 더한다.
방향을 돌려가면서 경우의 수를 찾을때 %4(4방향)을 사용한다.
- 코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int dy[] = { -1,0,1,0 };
const int dx[] = { 0,1,0,-1 };
int n, m, _map[10][10], temp[10][10], result = 99999999;
vector<pair<int, int>> v;
bool CheckOver(int ny, int nx)
{
if (ny < n && ny >= 0 && nx < m && nx >= 0 && _map[ny][nx] != 6)
{
return true;
}
return false;
}
vector<pair<int, int>> extendCCTV(int here, int direction)
{
vector<pair<int, int>> _change;
int y = v[here].first;
int x = v[here].second;
if (_map[y][x] == 1) // 1방향 카메라
{
while (1)
{
int ny = y + dy[direction];
int nx = x + dx[direction];
if (CheckOver(ny,nx))
{
if (_map[ny][nx] == 0)
{
_map[ny][nx] = '#';
_change.push_back({ ny,nx });
}
y = ny;
x = nx;
}
else
{
break;
}
}
}
else if (_map[y][x] == 2) // 2방향 앞뒤 카메라
{
for (int i = 0; i <= 2; i += 2)
{
int _y = y;
int _x = x;
while (1)
{
int ny = _y + dy[(direction + i) % 4];
int nx = _x + dx[(direction + i) % 4];
if (CheckOver(ny, nx))
{
if (_map[ny][nx] == 0)
{
_map[ny][nx] = '#';
_change.push_back({ ny,nx });
}
_y = ny;
_x = nx;
}
else
{
break;
}
}
}
}
else if (_map[y][x] == 3) // 2방향 직각 카메라
{
for (int i = 0; i < 2; i++)
{
int _y = y;
int _x = x;
while (1)
{
int ny = _y + dy[(direction + i) % 4];
int nx = _x + dx[(direction + i) % 4];
if (CheckOver(ny, nx))
{
if (_map[ny][nx] == 0)
{
_map[ny][nx] = '#';
_change.push_back({ ny,nx });
}
_y = ny;
_x = nx;
}
else
{
break;
}
}
}
}
else if (_map[y][x] == 4) // 3방향 카메라
{
for (int i = 0; i < 3; i++)
{
int _y = y;
int _x = x;
while (1)
{
int ny = _y + dy[(direction + i) % 4];
int nx = _x + dx[(direction + i) % 4];
if (CheckOver(ny, nx))
{
if (_map[ny][nx] == 0)
{
_map[ny][nx] = '#';
_change.push_back({ ny,nx });
}
_y = ny;
_x = nx;
}
else
{
break;
}
}
}
}
else if (_map[y][x] == 5) // 4방향 카메라
{
for (int i = 0; i < 4; i++)
{
int _y = y;
int _x = x;
while (1)
{
int ny = _y + dy[(direction + i) % 4];
int nx = _x + dx[(direction + i) % 4];
if (CheckOver(ny, nx))
{
if (_map[ny][nx] == 0)
{
_map[ny][nx] = '#';
_change.push_back({ ny,nx });
}
_y = ny;
_x = nx;
}
else
{
break;
}
}
}
}
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 (_map[i][j] == 0)
{
cnt++;
}
}
}
result = min(cnt, result);
return;
}
for (int i = 0; i < 4; i++)
{
vector<pair<int, int>> _change = extendCCTV(here, i);
dfs(here + 1);
for (auto b : _change)
{
_map[b.first][b.second] = 0;
}
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> _map[i][j];
if (_map[i][j] != 6 && _map[i][j] != 0)
{
v.push_back({ i,j });
}
}
}
dfs(0);
cout << result;
return 0;
}15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감
www.acmicpc.net
'C++ > BOJ' 카테고리의 다른 글
| [C++]/백준 2170번 선 긋기 (0) | 2024.03.26 |
|---|---|
| [C++]/백준 17822번 원판 돌리기 (0) | 2024.03.26 |
| [C++]/백준 1912번 연속합 (0) | 2024.03.26 |
| [C++]/백준 2632번 피자판매 (0) | 2024.03.26 |
| [C++]/백준 17143번 낚시왕 (0) | 2024.03.26 |