BOJ 15683 : 감시 (삼성 SW TEST A형)

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/1152 (A형 문제집)

 

www.acmicpc.net/problem/15683

 

이후 설명 및 입/출력은 링크 참고

 

먼저 모든 카메라가 방향을 가르키게 하기 위해, input에서 camera의 좌표를 따로 저장해두자.

그리고, 5번 카메라의 경우는 방향이 없으므로 따로 모은다.

MAP의 경우는 모두 6으로 만든 후, (1, 1)부터 MAP을 만들자. 

주변을 미리 벽으로 만들면, 경계 조건을 체크하지 않아도 되기 때문이다.

void input()
{
	scanf("%d %d", &N, &M);

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= M + 1; c++)
			MAP[r][c] = 6; /* 벽 */

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
		{
			int in;

			scanf("%d", &in);
			MAP[r][c] = in;

			if (in == 5)
			{
				camera5[cidx5].r = r;
				camera5[cidx5++].c = c;

				continue;
			}

			if (0 < in && in < 6)
			{
				camera[cidx].r = r;
				camera[cidx].c = c;
				camera[cidx++].number = in;
			}
		}
	}
	
	return;
}

 

이제 camera 좌표와 방향을 넣으면 벽이 나올 때 까지, '#'으로 만드는 함수를 만들자.

dr, dc 배열을 선언해서, 해당 방향으로 while문을 이용하면 된다.

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0,-1,0,1 };
int dc[] = { -1,0,1,0 };

void cctvScan(int map[][MAX], CAMERA camera, int dir)
{
	int r, c, cnt;

	r = camera.r;
	c = camera.c;

	while (1) 
	{
		r = r + dr[dir];
		c = c + dc[dir];
		
		if (map[r][c] == 6) return;   /* 벽에서는 종료 */

		map[r][c] = '#';
	}
}

벽이 나오면 종료, 그렇지 않으면 '#'을 넣어두자, 이때, 카메라를 통과할 수 있으므로, 카메라도 '#'으로 만들자.

카메라의 좌표는 따로 모아뒀기 때문에, MAP에서 카메라 표시가 사라져도 된다.

 

이제 카메라 번호마다 scan을 하도록 만들어보자.

 

카메라 번호와 방향(dir) 0~3이 주어질 경우,

1번 카메라 - 지정된 방향에 '#' 표시

2번 카메라 - 지정된 방향과 반대 방향에 '#' 표시

3번 카메라 - 지정된 방향과 다음 방향에 '#' 표시

4번 카메라 - 지정된 방향을 제외하고 '#' 표시

 

2번과 3번의 추가 방향은 if문으로 하드코딩 했다. 배열을 이용하거나, % 연산자를 써도 된다.

A형에서는 pass가 목표이므로, 디버깅 하기 쉬운 코드로 작성하자.

void cctvOn(int map[][MAX], CAMERA camera, int dir)
{
	switch (camera.number)
	{
	case 1:
		cctvScan(map, camera, dir);
		break;
	case 2:
	{
		int inverse = dir + 2;
		if (inverse > 3) inverse -= 4;

		cctvScan(map, camera, dir);
		cctvScan(map, camera, inverse);
		break;
	}
	case 3:
	{
		int nextDir = dir + 1;
		if (nextDir == 4) nextDir = 0;

		cctvScan(map, camera, dir);
		cctvScan(map, camera, nextDir);
		break;
	}
	case 4:
		for (int i = 0; i < 4; i++)
		{
			if (i == dir) continue;
			cctvScan(map, camera, i);
		}
		break;

	default:
		break;
	}
}

 

마지막으로, DFS를 이용하여, cctv를 모든 방향에 대해 켜도록 하자.

그 전에, 5번 방향은 '#'을 미리 표시하자.

for (int i = 0; i < cidx5; i++) /* 모든 5번 카메라 */
{
	for(int dir = 0; dir < 4; dir++) 
		cctvScan(MAP, camera5[i], dir); /* 4방향 모두 '#' 표시 */
}

...

DFS(0, map);

int MIN = 0x7fff0000;
void DFS(int L, int map[][MAX])
{
	if (L == cidx) /* 모든 카메라 방향 설정 완료 */
	{
		int tmp = getBlindSpot(map); /* map에서 0번 칸 count */

		if (tmp < MIN) MIN = tmp;

		return;
	}

	int copyMAP[MAX][MAX];
	
	for (int dir = 0; dir < 4; dir++)
	{
		if (camera[L].number == 2 && dir > 2) return; /* 2번 방향은 2번이면 충분 */

		copy(copyMAP, map);
		
		cctvOn(copyMAP, camera[L], dir);
		
		DFS(L + 1, copyMAP);
	}
}

 

마지막 사각 지대는 아래 처럼 간단히 세면 된다.

int getBlindSpot(int map[][MAX])
{
	int cnt = 0;
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			cnt += !map[r][c];

	return cnt;
}

 

전체 코드는 아래와 같다.

#include <stdio.h>

#define MAX (10 + 2)

int N, M;

int MAP[MAX][MAX];

typedef struct st {
	int r;
	int c;
	int number;
}CAMERA;

CAMERA camera[8 + 2]; 
CAMERA camera5[8 + 2];
int cidx;
int cidx5;

void input()
{
	scanf("%d %d", &N, &M);

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= M + 1; c++)
			MAP[r][c] = 6; /* 벽 */

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
		{
			int in;

			scanf("%d", &in);
			MAP[r][c] = in;

			if (in == 5)
			{
				camera5[cidx5].r = r;
				camera5[cidx5++].c = c;

				continue;
			}

			if (0 < in && in < 6)
			{
				camera[cidx].r = r;
				camera[cidx].c = c;
				camera[cidx++].number = in;
			}
		}
	}
	
	return;
}

void output(int map[][MAX]) 
{
	for (int r = 0; r <= N + 1; r++)
	{
		for (int c = 0; c <= M + 1; c++)
			printf("%d ", MAP[r][c]);
		putchar('\n');
	}
}

void copy(int dest[][MAX], int src[][MAX])
{
	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= M + 1; c++)
			dest[r][c] = src[r][c];
}

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0,-1,0,1 };
int dc[] = { -1,0,1,0 };

void cctvScan(int map[][MAX], CAMERA camera, int dir)
{
	int r, c, cnt;

	r = camera.r;
	c = camera.c;

	while (1) 
	{
		r = r + dr[dir];
		c = c + dc[dir];
		
		if (map[r][c] == 6) return;   /* 벽에서는 종료 */

		map[r][c] = '#';
	}
}

void cctvOn(int map[][MAX], CAMERA camera, int dir)
{
	switch (camera.number)
	{
	case 1:
		cctvScan(map, camera, dir);
		break;
	case 2:
	{
		int inverse = dir + 2;
		if (inverse > 3) inverse -= 4;

		cctvScan(map, camera, dir);
		cctvScan(map, camera, inverse);
		break;
	}
	case 3:
	{
		int nextDir = dir + 1;
		if (nextDir == 4) nextDir = 0;

		cctvScan(map, camera, dir);
		cctvScan(map, camera, nextDir);
		break;
	}
	case 4:
		for (int i = 0; i < 4; i++)
		{
			if (i == dir) continue;
			cctvScan(map, camera, i);
		}
		break;

	default:
		break;
	}
}

int getBlindSpot(int map[][MAX])
{
	int cnt = 0;
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			cnt += !map[r][c];

	return cnt;
}

int MIN = 0x7fff0000;
void DFS(int L, int map[][MAX])
{
	if (L == cidx)
	{
		int tmp = getBlindSpot(map);

		if (tmp < MIN) MIN = tmp;

		return;
	}

	int copyMAP[MAX][MAX];
	
	for (int dir = 0; dir < 4; dir++)
	{

		if (camera[L].number == 2 && dir > 2) return;

		copy(copyMAP, map);
		
		cctvOn(copyMAP, camera[L], dir);
		
		DFS(L + 1, copyMAP);
	}
}

int main(void)
{
	input();

	for (int i = 0; i < cidx5; i++)
	{
		for(int dir = 0; dir < 4; dir++)
			cctvScan(MAP, camera5[i], dir);
	}

	int map[MAX][MAX];

	copy(map, MAP);

	DFS(0, map);

	printf("%d\n", MIN);

	return 0;
}

 

A형은 tc가 여러 개이므로, MIN을 초기화 하는 것을 잊지말자.