BOJ 14502 : 연구소 (삼성 SW TEST A형)

삼성 A형 전체 링크

 

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

 

www.acmicpc.net/problem/14502

 

 

MAP을 입력받을 때, (0, 0)이 아닌 (1, 1)을 기준으로 잡는다.

(0, 0) ~ (N+1, N+1)을 모두 1로 만들고 (1, 1)부터 입력을 받으면, 

경계 조건을 신경쓰지 않고, 벽인지 아닌지만 체크하면 된다.

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] = 1;

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			scanf("%d", &MAP[r][c]);
}

 

이제 MAP을 입력받았으니, 벽을 3개 만들자.

벽을 만들 때, 3중 for문을 이용할 수도 있지만, DFS 연습으로, 3단계를 걸쳐 벽을 만들어 보자.

void DFS(int L, int sr)
{
	int tmp;
	if (L > 3) /* 3개의 벽을 만들었다면 */
	{
		for (int r = 0; r <= N + 1; r++)
			for (int c = 0; c <= M + 1; c++)
				tmpMAP[r][c] = MAP[r][c]; /* 만든 벽을 복사 */

		ALLBFS(); /* BFS로 바이러스를 퍼뜨린다. */
		tmp = countSafe(); /* 안전 구역을 센다 */

		if (tmp > max) max = tmp; /* 최대 안전 구역 갱신 */
		return;
	}

	for (int r = sr; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
		{
        	/* 벽이 아닌 곳은 통과 */
			if (MAP[r][c] != 0) continue;

			MAP[r][c] = 1; /* 벽을 만들고 */
			DFS(L + 1, r);   /* 다음 단계로 보내자 */
			MAP[r][c] = 0; /* DFS 종료 후 만든 벽은 제거 */
		}
	}
}

 

이제 바이러스를 퍼뜨리자, 바이러스를 찾으면, BFS로 퍼뜨려야한다.

하지만 벽이 존재하므로, 모든 벽을 scan하면서 모든 바이러스를 퍼뜨려야 한다.

이때, 원본 MAP의 보존을 위해, tmpMAP에 복사한 후 퍼뜨려야 한다. (BFS)

(바이러스를 퍼뜨리는 연습문제는 토마토 참고)

void BFS(int r, int c)
{
	wp = rp = 0; /* queue 초기화 */

	queue[wp].r = r; 
	queue[wp++].c = c; /* 바이러스가 있는 곳의 좌표를 push */

	while (wp > rp)
	{
		out = queue[rp++]; /* queue pop */
        
		for (int i = 0; i < 4; i++) /* 4방향으로 바이러스를 퍼뜨리자 */
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (tmpMAP[nr][nc] == 0) /* 벽이 아닌 곳, 즉 빈칸은 바이러스가 된다 */
			{
				tmpMAP[nr][nc] = 2; /* 바이러스 표시 */
                
				queue[wp].r = nr;
				queue[wp++].c = nc; /* 바이러스가 된 곳을 다시 queue에 push */
			}
		}
	}
}

void ALLBFS()
{
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++) /* 바이러스를 찾아서 퍼뜨리자 */
			if (tmpMAP[r][c] == 2) BFS(r, c);
}

 

바이러스를 모두 퍼뜨리면 안전 구역을 셀 수 있다.

DFS ( L > 3 )에서 countSafe 함수로 tmpMAP의 0인 부분을 세면 된다.

int countSafe()
{
	int sum = 0;

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			sum += !tmpMAP[r][c];

	return sum;
}

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (15)

int N, M;
int MAP[MAX][MAX];
int tmpMAP[MAX][MAX];

typedef struct st
{
	int r;
	int c;
}QUEUE;

QUEUE queue[MAX*MAX];
int wp, rp;

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] = 1;

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			scanf("%d", &MAP[r][c]);
}

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

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

void BFS(int r, int c)
{
	wp = rp = 0;

	queue[wp].r = r;
	queue[wp++].c = c;

	while (wp > rp)
	{
		QUEUE out = queue[rp++];
		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (tmpMAP[nr][nc] == 0)
			{
				tmpMAP[nr][nc] = 2;
				queue[wp].r = nr;
				queue[wp++].c = nc;
			}
		}
	}
}

void ALLBFS()
{
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			if (tmpMAP[r][c] == 2) BFS(r, c);
}

int countSafe()
{
	int sum = 0;

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			sum += !tmpMAP[r][c];

	return sum;
}

int max = 0;
void DFS(int L, int sr)
{
	int tmp;
	if (L > 3)
	{
		for (int r = 0; r <= N + 1; r++)
			for (int c = 0; c <= M + 1; c++)
				tmpMAP[r][c] = MAP[r][c];

		ALLBFS();
		tmp = countSafe();

		if (tmp > max) max = tmp;
		return;
	}

	for (int r = sr; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
		{
			if (MAP[r][c] != 0) continue;

			MAP[r][c] = 1;
			DFS(L + 1, r);
			MAP[r][c] = 0;
		}
	}
}

int main(void)
{
	input();

	DFS(1, 1);

	printf("%d\n", max);
    
	return 0;
}

 

실제 A형은 tc가 여러개이므로 max와 map을 잘 초기화 하자.