감시
https://www.acmicpc.net/problem/15683
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 37014 | 17265 | 10338 | 43.494% |
문제
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다.
사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다.
각 CCTV가 감시할 수 있는 방법은 다음과 같다.
1번 CCTV는 한 쪽 방향만 감시할 수 있다.
2번과 3번은 두 방향을 감시할 수 있는데,
2번은 감시하는 방향이 서로 반대방향이어야 하고,
3번은 직각 방향이어야 한다.
4번은 세 방향, 5번은 네 방향을 감시할 수 있다.
CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다.
사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다.
CCTV가 감시할 수 없는 영역은 사각지대라고 한다.
CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.
지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호이다.
위의 예시에서 1번의 방향에 따라 감시할 수 있는 영역을 ‘#‘로 나타내면 아래와 같다.
CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 칸을 감시할 수 없다.
위의 예시에서 감시할 수 있는 방향을 알아보면 아래와 같다.
CCTV는 CCTV를 통과할 수 있다. 아래 예시를 보자.
위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.
사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다.
0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.
CCTV의 최대 개수는 8개를 넘지 않는다.
출력
첫째 줄에 사각 지대의 최소 크기를 출력한다.
예제 입력 1
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 0
예제 출력 1
20
예제 입력 2
6 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
예제 출력 2
15
예제 입력 3
6 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 1
예제 출력 3
6
예제 입력 4
6 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 1
예제 출력 4
2
예제 입력 5
1 7 0 1 2 3 4 5 6
예제 출력 5
0
예제 입력 6
3 7 4 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 4
예제 출력 6
0
출처
- 문제를 만든 사람: baekjoon
알고리즘 분류
추가 반례
https://www.acmicpc.net/board/search/all/problem/15683
예제 입력 A
8 8 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
예제 출력 A
0
예제 입력 B
8 8 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0
예제 출력 B
12
예제 입력 C
4 6 2 6 0 3 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 1
예제 출력 C
8
예제 입력 D
5 5 6 0 6 6 0 6 4 2 0 0 2 6 0 4 6 6 6 0 6 6 0 0 0 6 6
예제 출력 D
3
예제 입력 E
6 6 0 0 0 0 0 0 0 0 6 0 0 0 6 0 1 0 6 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0
예제 출력 E
30
예제 입력 F
4 6 0 0 0 1 0 1 6 6 6 0 6 6 0 0 0 1 6 6 6 6 6 0 6 6
예제 출력 F
0
예제 입력 G
8 5 6 6 0 0 6 6 6 6 2 0 0 6 6 4 0 0 6 3 0 6 0 0 0 5 0 0 0 6 6 0 0 0 6 0 4 0 6 6 6 0
예제 출력 G
8
예제 입력 H
7 5 6 0 0 0 6 0 4 1 6 6 6 0 6 0 6 0 6 0 3 6 0 6 0 1 6 6 6 0 5 6 6 6 6 5 6
예제 출력 H
3
예제 입력 I
7 7 6 0 0 0 0 0 6 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 4 1 0 0 0 0 6 0 0 0 6 3 0 2 0
예제 출력 I
15
첫번째 줄에는 사무실의 크기는 세로 크기 N과 가로 크기 M (1 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보를 담는다.
입력 확인 코드
#include <iostream>
using namespace std;
constexpr auto MAX = 8;
int map[MAX][MAX];
// N 세로, M 가로
int N, M;
bool debugBool = true;
// 시각적인 디버그용 함수
void DebugPrint()
{
cout << "\n";
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cout << map[i][j] << " ";
}
cout << "\n";
}
}
// 프로그램 시작시 초기화
void Initialization()
{
// 맵의 모든 부분을 빈 공간으로 초기화 시켜줍니다.
for (int i = 0; i < MAX; i++)
{
for (int j = 0; j < MAX; j++)
{
map[i][j] = 0;
}
}
}
// 문제의 입력을 받습니다.
void ReceiveInput()
{
cin >> N >> M;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> map[i][j];
}
}
}
int main()
{
Initialization();
ReceiveInput();
if (debugBool) DebugPrint();
return 0;
}
CCTV의 위치와 종류를 저장이 필요 (구조체로 저장)
CCTV의 최대 개수는 8개를 넘지 않는다.
#include <iostream>
using namespace std;
constexpr auto MAX = 8;
int map[MAX][MAX];
// N 세로, M 가로
int N, M;
bool debugBool = true;
// CCTV의 타입은 기본으로 -1
struct CCTVInformation
{
int type = -1;
int x, y;
} CCTV[MAX];
// 시각적인 디버그용 함수
void DebugPrint()
{
cout << "\n";
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cout << map[i][j] << " ";
}
cout << "\n";
}
cout << "\n";
for (int i = 0; i < MAX; i++)
{
if (CCTV[i].type != -1)
{
cout << "CCTV[i].type : " << CCTV[i].type << " CCTV[i].x : " << CCTV[i].x << " CCTV[i].y : " << CCTV[i].y << "\n";
}
}
}
// 프로그램 시작시 초기화
void Initialization()
{
// 맵의 모든 부분을 빈 공간으로 초기화 시켜줍니다.
for (int i = 0; i < MAX; i++)
{
for (int j = 0; j < MAX; j++)
{
map[i][j] = 0;
}
}
}
// 문제의 입력을 받습니다.
void ReceiveInput()
{
cin >> N >> M;
// CCTV 숫자를 위한 임시
int temp = 0;
int temp2 = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> temp2;
map[i][j] = temp2;
if (temp2 > 0 && temp2 != 6)
{
CCTV[temp].type = temp2;
CCTV[temp].x = i;
CCTV[temp].y = j;
temp++;
}
}
}
}
int main()
{
Initialization();
ReceiveInput();
if (debugBool) DebugPrint();
return 0;
}
CCTV의 Type마다 다른 기능을 구현하고 모든 경우의 수를 Map에 마킹하여 빈 공간을 처리할 생각
메모리가 512MB로 넉넉하고 시간도 적당할 것이라 생각
CCTV가 보는 곳을 수로 체크하려다보니 벽의 숫자가 6이라 문제가 발생하여 벽을 -1로 변경하였다.
#include <iostream>
using namespace std;
constexpr auto MAX = 8;
int map[MAX][MAX];
// N 세로, M 가로
int N, M;
bool debugBool = true;
// CCTV의 타입은 기본으로 -1
struct CCTVInformation
{
int type = -1;
int x, y;
} CCTV[MAX];
// 시각적인 디버그용 함수
void DebugPrint()
{
cout << "\n";
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cout << map[i][j] << " ";
}
cout << "\n";
}
cout << "\n";
for (int i = 0; i < MAX; i++)
{
if (CCTV[i].type != -1)
{
cout << "CCTV[i].type : " << CCTV[i].type << " CCTV[i].x : " << CCTV[i].x << " CCTV[i].y : " << CCTV[i].y << "\n";
}
}
}
// 프로그램 시작시 초기화
void Initialization()
{
// 맵의 모든 부분을 빈 공간으로 초기화 시켜줍니다.
for (int i = 0; i < MAX; i++)
{
for (int j = 0; j < MAX; j++)
{
map[i][j] = 0;
}
}
}
// 문제의 입력을 받습니다.
void ReceiveInput()
{
cin >> N >> M;
// CCTV 숫자를 위한 임시
int temp = 0;
int temp2 = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> temp2;
if (temp2 == 6) {
map[i][j] = -1;
}
else {
map[i][j] = temp2;
}
if (temp2 > 0 && temp2 != 6) {
CCTV[temp].type = temp2;
CCTV[temp].x = i;
CCTV[temp].y = j;
temp++;
}
}
}
}
int main()
{
Initialization();
ReceiveInput();
if (debugBool) DebugPrint();
return 0;
}
통과된 코드
#include <iostream>
using namespace std;
constexpr auto MAX = 8;
int map[MAX][MAX];
// N 세로, M 가로
int N, M, MinBlindSpot;
bool debugBool = false;
// 우 상 좌 하
int dxdy[4][2] = { {0, 1}, {-1, 0}, {0, -1}, {1, 0} };
// CCTV의 타입은 기본으로 -1
struct CCTVInformation
{
int type = -1;
int x = 0;
int y = 0;
} CCTV[MAX];
// 시각적인 디버그용 함수
void DebugPrint()
{
cout << "\n";
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cout << map[i][j] << " ";
}
cout << "\n";
}
cout << "\n";
for (int i = 0; i < MAX; i++) {
if (CCTV[i].type != -1)
{
cout << "CCTV[i].type : " << CCTV[i].type << " CCTV[i].x : " << CCTV[i].x << " CCTV[i].y : " << CCTV[i].y << "\n";
}
}
}
// 프로그램 시작시 초기화
void Initialization()
{
MinBlindSpot = 64;
// 맵의 모든 부분을 빈 공간으로 초기화 시켜줍니다.
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
map[i][j] = 0;
}
}
}
// 문제의 입력을 받습니다.
void ReceiveInput()
{
cin >> N >> M;
// CCTV 숫자를 위한 임시
int temp = 0;
int temp2 = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> temp2;
if (temp2 == 6) {
map[i][j] = -1;
}
else {
map[i][j] = temp2;
}
if (temp2 > 0 && temp2 != 6) {
CCTV[temp].type = temp2;
CCTV[temp].x = i;
CCTV[temp].y = j;
temp++;
}
}
}
}
// CCTV가 타입마다 할 수 있는 행등을 구현한 함수입니다.
void MarkingMap(int dir, int CCTVNumber, int check)
{
switch (CCTV[CCTVNumber].type) {
case 1:
switch (dir) {
case 0: // 1번 타입 카메라 우측 감시 또는 해제
for (int i = CCTV[CCTVNumber].y + 1 ; i < M; i++) {
if (map[CCTV[CCTVNumber].x][i] == -1) break;
map[CCTV[CCTVNumber].x][i] += CCTV[CCTVNumber].type * check;
}
break;
case 1: // 1번 타입 카메라 좌측 감시 또는 해제
for (int i = CCTV[CCTVNumber].y - 1; i >= 0; i--) {
if (map[CCTV[CCTVNumber].x][i] == -1) break;
map[CCTV[CCTVNumber].x][i] += CCTV[CCTVNumber].type * check;
}
break;
case 2: // 1번 타입 카메라 아래 감시 또는 해제
for (int i = CCTV[CCTVNumber].x + 1; i < N; i++) {
if (map[i][CCTV[CCTVNumber].y] == -1) break;
map[i][CCTV[CCTVNumber].y] += CCTV[CCTVNumber].type * check;
}
break;
case 3: // 1번 타입 카메라 위 감시 또는 해제
for (int i = CCTV[CCTVNumber].x - 1; i >= 0; i--) {
if (map[i][CCTV[CCTVNumber].y] == -1) break;
map[i][CCTV[CCTVNumber].y] += CCTV[CCTVNumber].type * check;
}
break;
}
break;
case 2:
switch (dir) {
case 0: // 2번 타입 카메라 우측 감시 또는 해제
for (int i = CCTV[CCTVNumber].y + 1; i < M; i++) {
if (map[CCTV[CCTVNumber].x][i] == -1) break;
map[CCTV[CCTVNumber].x][i] += CCTV[CCTVNumber].type * check;
}
// 2번 타입 카메라 좌측 감시 또는 해제
for (int i = CCTV[CCTVNumber].y - 1; i >= 0; i--) {
if (map[CCTV[CCTVNumber].x][i] == -1) break;
map[CCTV[CCTVNumber].x][i] += CCTV[CCTVNumber].type * check;
}
break;
case 1: // 2번 타입 카메라 아래 감시 또는 해제
for (int i = CCTV[CCTVNumber].x + 1; i < N; i++) {
if (map[i][CCTV[CCTVNumber].y] == -1) break;
map[i][CCTV[CCTVNumber].y] += CCTV[CCTVNumber].type * check;
}
// 2번 타입 카메라 위 감시 또는 해제
for (int i = CCTV[CCTVNumber].x - 1; i >= 0; i--) {
if (map[i][CCTV[CCTVNumber].y] == -1) break;
map[i][CCTV[CCTVNumber].y] += CCTV[CCTVNumber].type * check;
}
break;
case 2:
break;
case 3:
break;
}
break;
case 3:
switch (dir) {
case 0: // 3번 타입 카메라 우측 감시 또는 해제
for (int i = CCTV[CCTVNumber].y + 1; i < M; i++) {
if (map[CCTV[CCTVNumber].x][i] == -1) break;
map[CCTV[CCTVNumber].x][i] += CCTV[CCTVNumber].type * check;
}
// 3번 타입 카메라 위 감시 또는 해제
for (int i = CCTV[CCTVNumber].x - 1; i >= 0; i--) {
if (map[i][CCTV[CCTVNumber].y] == -1) break;
map[i][CCTV[CCTVNumber].y] += CCTV[CCTVNumber].type * check;
}
break;
case 1: // 3번 타입 카메라 위 감시 또는 해제
for (int i = CCTV[CCTVNumber].x - 1; i >= 0; i--) {
if (map[i][CCTV[CCTVNumber].y] == -1) break;
map[i][CCTV[CCTVNumber].y] += CCTV[CCTVNumber].type * check;
}
// 3번 타입 카메라 좌측 감시 또는 해제
for (int i = CCTV[CCTVNumber].y - 1; i >= 0; i--) {
if (map[CCTV[CCTVNumber].x][i] == -1) break;
map[CCTV[CCTVNumber].x][i] += CCTV[CCTVNumber].type * check;
}
break;
case 2: // 3번 타입 카메라 좌측 감시 또는 해제
for (int i = CCTV[CCTVNumber].y - 1; i >= 0; i--) {
if (map[CCTV[CCTVNumber].x][i] == -1) break;
map[CCTV[CCTVNumber].x][i] += CCTV[CCTVNumber].type * check;
}
// 3번 타입 카메라 아래 감시 또는 해제
for (int i = CCTV[CCTVNumber].x + 1; i < N; i++) {
if (map[i][CCTV[CCTVNumber].y] == -1) break;
map[i][CCTV[CCTVNumber].y] += CCTV[CCTVNumber].type * check;
}
break;
case 3: // 3번 타입 카메라 아래 감시 또는 해제
for (int i = CCTV[CCTVNumber].x + 1; i < N; i++) {
if (map[i][CCTV[CCTVNumber].y] == -1) break;
map[i][CCTV[CCTVNumber].y] += CCTV[CCTVNumber].type * check;
}
// 3번 타입 카메라 우측 감시 또는 해제
for (int i = CCTV[CCTVNumber].y + 1; i < M; i++) {
if (map[CCTV[CCTVNumber].x][i] == -1) break;
map[CCTV[CCTVNumber].x][i] += CCTV[CCTVNumber].type * check;
}
break;
}
break;
case 4:
switch (dir) {
case 0:
// 4번 타입 카메라 위 감시 또는 해제
for (int i = CCTV[CCTVNumber].x - 1; i >= 0; i--) {
if (map[i][CCTV[CCTVNumber].y] == -1) break;
map[i][CCTV[CCTVNumber].y] += CCTV[CCTVNumber].type * check;
}
// 4번 타입 카메라 좌측 감시 또는 해제
for (int i = CCTV[CCTVNumber].y - 1; i >= 0; i--) {
if (map[CCTV[CCTVNumber].x][i] == -1) break;
map[CCTV[CCTVNumber].x][i] += CCTV[CCTVNumber].type * check;
}
// 4번 타입 카메라 아래 감시 또는 해제
for (int i = CCTV[CCTVNumber].x + 1; i < N; i++) {
if (map[i][CCTV[CCTVNumber].y] == -1) break;
map[i][CCTV[CCTVNumber].y] += CCTV[CCTVNumber].type * check;
}
break;
case 1: // 4번 타입 카메라 우측 감시 또는 해제
for (int i = CCTV[CCTVNumber].y + 1; i < M; i++) {
if (map[CCTV[CCTVNumber].x][i] == -1) break;
map[CCTV[CCTVNumber].x][i] += CCTV[CCTVNumber].type * check;
}
// 4번 타입 카메라 좌측 감시 또는 해제
for (int i = CCTV[CCTVNumber].y - 1; i >= 0; i--) {
if (map[CCTV[CCTVNumber].x][i] == -1) break;
map[CCTV[CCTVNumber].x][i] += CCTV[CCTVNumber].type * check;
}
// 4번 타입 카메라 아래 감시 또는 해제
for (int i = CCTV[CCTVNumber].x + 1; i < N; i++) {
if (map[i][CCTV[CCTVNumber].y] == -1) break;
map[i][CCTV[CCTVNumber].y] += CCTV[CCTVNumber].type * check;
}
break;
case 2: // 4번 타입 카메라 우측 감시 또는 해제
for (int i = CCTV[CCTVNumber].y + 1; i < M; i++) {
if (map[CCTV[CCTVNumber].x][i] == -1) break;
map[CCTV[CCTVNumber].x][i] += CCTV[CCTVNumber].type * check;
}
// 4번 타입 카메라 위 감시 또는 해제
for (int i = CCTV[CCTVNumber].x - 1; i >= 0; i--) {
if (map[i][CCTV[CCTVNumber].y] == -1) break;
map[i][CCTV[CCTVNumber].y] += CCTV[CCTVNumber].type * check;
}
// 4번 타입 카메라 아래 감시 또는 해제
for (int i = CCTV[CCTVNumber].x + 1; i < N; i++) {
if (map[i][CCTV[CCTVNumber].y] == -1) break;
map[i][CCTV[CCTVNumber].y] += CCTV[CCTVNumber].type * check;
}
break;
case 3: // 4번 타입 카메라 우측 감시 또는 해제
for (int i = CCTV[CCTVNumber].y + 1; i < M; i++) {
if (map[CCTV[CCTVNumber].x][i] == -1) break;
map[CCTV[CCTVNumber].x][i] += CCTV[CCTVNumber].type * check;
}
// 4번 타입 카메라 위 감시 또는 해제
for (int i = CCTV[CCTVNumber].x - 1; i >= 0; i--) {
if (map[i][CCTV[CCTVNumber].y] == -1) break;
map[i][CCTV[CCTVNumber].y] += CCTV[CCTVNumber].type * check;
}
// 4번 타입 카메라 좌측 감시 또는 해제
for (int i = CCTV[CCTVNumber].y - 1; i >= 0; i--) {
if (map[CCTV[CCTVNumber].x][i] == -1) break;
map[CCTV[CCTVNumber].x][i] += CCTV[CCTVNumber].type * check;
}
break;
}
break;
case 5:
switch (dir){
case 0: // 5번 타입 카메라 우측 감시 또는 해제
for (int i = CCTV[CCTVNumber].y + 1; i < M; i++) {
if (map[CCTV[CCTVNumber].x][i] == -1) break;
map[CCTV[CCTVNumber].x][i] += CCTV[CCTVNumber].type * check;
}
// 5번 타입 카메라 위 감시 또는 해제
for (int i = CCTV[CCTVNumber].x - 1; i >= 0; i--) {
if (map[i][CCTV[CCTVNumber].y] == -1) break;
map[i][CCTV[CCTVNumber].y] += CCTV[CCTVNumber].type * check;
}
// 5번 타입 카메라 좌측 감시 또는 해제
for (int i = CCTV[CCTVNumber].y - 1; i >= 0; i--) {
if (map[CCTV[CCTVNumber].x][i] == -1) break;
map[CCTV[CCTVNumber].x][i] += CCTV[CCTVNumber].type * check;
}
// 5번 타입 카메라 아래 감시 또는 해제
for (int i = CCTV[CCTVNumber].x + 1; i < N; i++) {
if (map[i][CCTV[CCTVNumber].y] == -1) break;
map[i][CCTV[CCTVNumber].y] += CCTV[CCTVNumber].type * check;
}
break;
case 1:
break;
case 2:
break;
case 3:
break;
}
break;
break;
}
}
// CCTV가 볼 수 있는 모든 경우의 수를 확인합니다.
void DFS(int cctvNumber)
{
// 만약 CCTV의 최대 개수를 넘거나 다음 CCTV가 없다면 빈 공간을 카운트 합니다.
if (cctvNumber == 8 || CCTV[cctvNumber].type == -1) {
int temp = 0;
// 사각지대를 카운트 합니다.
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (map[j][i] == 0){
temp++;
}
}
}
if (temp < MinBlindSpot) {
MinBlindSpot = temp;
}
return;
}
// 모든 경우의 수를 확인
for (int i = 0; i < 4; i++) {
switch (i)
{
case 0:
MarkingMap(i, cctvNumber, 1);
DFS(cctvNumber + 1);
MarkingMap(i, cctvNumber, -1);
break;
case 1:
MarkingMap(i, cctvNumber, 1);
DFS(cctvNumber + 1);
MarkingMap(i, cctvNumber, -1);
break;
case 2:
MarkingMap(i, cctvNumber, 1);
DFS(cctvNumber + 1);
MarkingMap(i, cctvNumber, -1);
break;
case 3:
MarkingMap(i, cctvNumber, 1);
DFS(cctvNumber + 1);
MarkingMap(i, cctvNumber, -1);
break;
}
}
}
int main()
{
Initialization();
ReceiveInput();
DFS(0);
cout << MinBlindSpot;
// 디버그용
if (debugBool) DebugPrint();
return 0;
}
CCTV가 볼 수 있는 모든 경우의 수
DFS를 사용하여 각 CCTV가 볼 수 있는 모든 경우의 수를 마킹하고 다음 CCTV가 없을 경우(-1) / 또는 최대 개수를 넘을 경우
Map에 모든 빈 공간을 카운트한다.
만약 카운트한 빈공간이 전보다 작다면 그 값을 대입해준다.
CCTV의 타입에 따른 기능 구현
일단 이렇게 구현하려고 해서 작성하기는 했지만 굉장히 비효율적인 방법이라고 생각한다.
각 CCTV의 타입마다 방향을 나누어 감시할 수 있는 방향을 전부 마킹해준다.
만약 벽을 만나면 break;
1번 CCTV – 4 / 2번 CCTV – 2 / 3번 CCTV – 4 / 4번 CCTV – 4 / 5번 CCTV – 1
총 15 가지의 기능 (대부분 복사 붙여넣기라 오래 걸리지는 않았다.)
구현은 제대로 했으나 계속 실패한 이유는 중간에 배열의 범위를 <=으로 체크하여 오류가 난 것
(왜 컴파일 할 때는 오류가 안 났는지….이해할 수 없다.)
이 오류 하나 찾느냐고 코드를 전부 갈아엎을뻔했다.
문제를 해결하고 다른 분들의 코드를 살펴보니 대부분 CCTV가 볼 수 있는 좌표를 저장하여 더 깔끔하게 처리…
나는 CCTV의 기능을 너무 더럽게 구현한 것 같아 너무 부끄럽다… 코드길이….
![백준 16486번 (운동장 한 바퀴, C++) [BAEKJOON]](https://lycos7560.com/wp-content/uploads/boj-og.png)
![백준 1074번 (Z, C++, DivideAndConquer) [BAEKJOON]](https://lycos7560.com/wp-content/uploads/2022/10/boj-og-1-2048x1070-1-1024x535.png)
![백준 2933번 (미네랄, C++, Simulation) / 추가 반례 [BAEKJOON]](https://lycos7560.com/wp-content/uploads/boj-og-1.png)