check 함수를 이용하여 해당 cctv의 좌표로 부터, 해당 방향에 대하여 감시여부를 체크하였습니다.
DFS를 이용하여 접근해보았습니다.
typedef struct { int row; // cctv의 좌표 int col; int type; // cctv의 type }CCTV;
CCTV cctv[8]; // cctv 정보를 담은 배열
int map[8][8], // 기본 map
visited[8][8]; // 해당 좌표가 감시되었는지 확인하는 배열
int N, M, result, num_cctv; // 가로 ,세로 , 최소 사각지대, cctv의 갯수
// cctv의 좌표와 check를 원하는 방향, opt를 입력 받습니다.
// 동쪽 0도 : dir == 0
// 북쪽 90도 : dir == 1
// 서쪽 180도 : dir == 2
// 남쪽 270도 : dir == 3
void Check(int row, int col, int dir, int opt) // opt가 0이면 visited 배열 의 해당좌표 값 증가, 1이면 감소 { switch (dir) { case 0: col++; while (col < M) { if (map[row][col] == 6) return; switch (opt) { case 0: visited[row][col]++; break; case 1: visited[row][col]--; break; } col++; }return;
case 1: row--; while (row >= 0) { if (map[row][col] == 6) return; switch (opt) { case 0: visited[row][col]++; break; case 1: visited[row][col]--; break; } row--; }return; ~~~~~~~~~~~~~~~~~~~~ 생략부분은 아래 소스코드 참조
// visited 배열과 map 배열을 확인해서 사각지대를 찾는 함수
int find_blind_spot(void) { int num = 0; for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) num = (visited[i][j] == 0 && map[i][j]== 0) ? num + 1 : num; return num; }
// DFS 함수, index는 cctv의 정보를 담고있는 ccctv 배열의 index, ccctv의 순서를 의미합니다. (index == 0 ~ num_cctv -1)
void Monitor(int index) { int blind, row = cctv[index].row, col = cctv[index].col, type = cctv[index].type;
// 탈출조건 if (index == num_cctv) {
blind = find_blind_spot(); // blind 는 사각지대의 수를 의미합니다. result = blind < result ? blind : result; // result는 이전까지의 최소 사각지대수를 의미합니다. return; }
// cctv의 종류 1~5에 따라 check함수를 실행합니다.
switch (type) { case 1: for (int i = 0; i < 4; i++) { Check(row, col, i, 0); Monitor(index + 1); Check(row, col, i, 1); }return; case 2:
sungjae940 5년 전
어디서 틀렸을까요? ㅠㅠ
typedef struct
{
int row; // cctv의 좌표
int col;
int type; // cctv의 type
}CCTV;
CCTV cctv[8]; // cctv 정보를 담은 배열
int map[8][8], // 기본 map
visited[8][8]; // 해당 좌표가 감시되었는지 확인하는 배열
int N, M, result, num_cctv; // 가로 ,세로 , 최소 사각지대, cctv의 갯수
// cctv의 좌표와 check를 원하는 방향, opt를 입력 받습니다.
// 동쪽 0도 : dir == 0
// 북쪽 90도 : dir == 1
// 서쪽 180도 : dir == 2
// 남쪽 270도 : dir == 3
void Check(int row, int col, int dir, int opt) // opt가 0이면 visited 배열 의 해당좌표 값 증가, 1이면 감소
{
switch (dir)
{
case 0:
col++;
while (col < M)
{
if (map[row][col] == 6) return;
switch (opt)
{
case 0: visited[row][col]++; break;
case 1: visited[row][col]--; break;
}
col++;
}return;
case 1:
row--;
while (row >= 0)
{
if (map[row][col] == 6) return;
switch (opt)
{
case 0: visited[row][col]++; break;
case 1: visited[row][col]--; break;
}
row--;
}return;
~~~~~~~~~~~~~~~~~~~~ 생략부분은 아래 소스코드 참조
// visited 배열과 map 배열을 확인해서 사각지대를 찾는 함수
int find_blind_spot(void)
{
int num = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
num = (visited[i][j] == 0 && map[i][j]== 0) ? num + 1 : num;
return num;
}
// DFS 함수, index는 cctv의 정보를 담고있는 ccctv 배열의 index, ccctv의 순서를 의미합니다. (index == 0 ~ num_cctv -1)
void Monitor(int index)
{
int blind, row = cctv[index].row, col = cctv[index].col, type = cctv[index].type;
// 탈출조건
if (index == num_cctv)
{
blind = find_blind_spot(); // blind 는 사각지대의 수를 의미합니다.
result = blind < result ? blind : result; // result는 이전까지의 최소 사각지대수를 의미합니다.
return;
}
// cctv의 종류 1~5에 따라 check함수를 실행합니다.
switch (type)
{
case 1:
for (int i = 0; i < 4; i++)
{
Check(row, col, i, 0);
Monitor(index + 1);
Check(row, col, i, 1);
}return;
case 2:
~~~~~~~~~~~~~~~~~~~~ 생략부분은 아래 소스코드 참조