sungjae940   5년 전

예제는 답이 나오는데 반례가 궁금합니다. 

어디서 틀렸을까요? ㅠㅠ

  1.  cctv 구조체를 선언해서 각 cctv의 좌표와 type을 저장했습니다.
  2. check 함수를 이용하여 해당 cctv의 좌표로 부터, 해당 방향에 대하여 감시여부를 체크하였습니다. 
  3. 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:

~~~~~~~~~~~~~~~~~~~~ 생략부분은 아래 소스코드 참조 


djm03178   5년 전

반례 목록 드립니다.

댓글을 작성하려면 로그인해야 합니다.