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

삼성 A형 전체 링크

 

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

 

www.acmicpc.net/problem/17142

 

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

연구소 문제와 다른 점은 벽을 세우는 것이 아니고, 바이러스를 M개 선택해야하는 것이다.

 

바이러스의 선택 → DFS 경우의 수 : 조합 문제 

바이러스의 확산 → 토마토 문제를 같이 조합해서 풀면 된다.

 

먼저 문제를 풀기 편하게 input을 받으면서 MAP을 재변경하자.

벽(1)과 바이러스(2)를 그대로 두면, 바이러스가 몇초 뒤에 퍼지는지 셀 때, 구분하기 까다롭다.

따라서 벽은 -1로, 바이러스는 -2로 표시하자.

또한, 바이러스는 따로 배열에 저장해두자.

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

RC virus[MAX*MAX];
int vcnt;

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

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			MAP[r][c] = -1;

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

			if (MAP[r][c] == 1) MAP[r][c] = -1;
			else if (MAP[r][c] == 2)
			{
				virus[vcnt].r = r;
				virus[vcnt++].c = c;

				MAP[r][c] = -2;
			}
		}
	}
}

 

바이러스를 모두 배열에 저장했으면, DFS를 이용해 바이러스를 선택한다.

start 변수를 이용하면 이미 선택한 바이러스는 다시 선택하지 않을 수 있다. (DFS 경우의 수 : 조합 문제 참고)

int MIN = 0x7fff0000;
void DFS(int L, int start)
{
	if (L > M)
	{
    	/* 바이러스 확산 */
		return;
	}

	for (int i = start; i < vcnt; i++)
	{
		MAP[virus[i].r][virus[i].c] = 1;
		DFS(L + 1, i + 1);
		MAP[virus[i].r][virus[i].c] = -2;
	}
}

 

바이러스를 선택한 곳에는 MAP에 1로 표시한다. DFS가 종료되면 다시 -2로 돌린다.

 

이제 선택한 바이러스를 2차원 BFS로 퍼뜨리자.

tmpMAP에 MAP을 복사하고, 활성화된 바이러스인 경우(MAP[r][c] = 1)에 큐에 담자.

그리고 dr, dc 배열을 이용하여 4방향 탐색을 하며 바이러스를 증식시키자.

증식된 바이러스는 이전 바이러스의 MAP에 +1을 더해준다.

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

void BFS()
{
	wp = rp = 0;
	for (int r = 0; r <= N + 1; r++)
	{
		for (int c = 0; c <= N + 1; c++)
		{
			tmpMAP[r][c] = MAP[r][c];
			
			if (MAP[r][c] == 1)
			{
				queue[wp].r = r;
				queue[wp++].c = c;
			}
		}
	}


	while (wp > rp)
	{
		RC 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)
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;

				tmpMAP[nr][nc] = tmpMAP[out.r][out.c] + 1;
			}
		}
	}
}

 

연구소 3이 까다로운 점은, 빈칸인 경우만 큐에 담는 것이 아니라, 비활성 바이러스도 담을 수 있다는 것이다.

문제는, 비활성 바이러스가 마지막에 담길 경우이다.

아래의 경우를 보자.

왼쪽의 바이러스는 활성화 되어 1로 변경되었고, 오른쪽의 바이러스는 비활성화 상태인 -2가 된다.

2차원 BFS를 실행하면 아래의 결과가 나오게 된다.

 

하지만 실제 문제의 조건의 결과는 아래와 같아야 한다.

문제의 조건은 모든 바이러스가 활성화가 되는 시간이 아닌, 모든 바이러스가 빈칸에 놓이는 시간이기 때문이다.

 

결론은 비활성 바이러스를 담을 때, 현재 바이러스가 마지막 바이러스인지 확인하고 담아야 하는 것이다.

따라서 배열에 현재 빈칸(0)이 있는지 check하고, 빈칸이 있다면 담는다.

int checkEmpty()
{
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			if (tmpMAP[r][c] == 0) return 1;

	return 0;
}

void BFS()
{
	/* ... */
    
	while (wp > rp)
	{
		RC 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) { ... } /* 빈칸인 경우 */
			else if (tmpMAP[nr][nc] == -2)   /* 비활성 바이러스인 경우 */
			{
				if (checkEmpty()) /* 빈칸이 있다면 */
				{
					queue[wp].r = nr;
					queue[wp++].c = nc;

					tmpMAP[nr][nc] = tmpMAP[out.r][out.c] + 1;
				}
			}
		}
	}
}

 

BFS가 종료되었다면, 모든 바이러스가 생성될 때까지 걸린 시간을 찾는다.

토마토 문제와 같은 원리로 1부터 셌으므로, 결과에서 -1을 빼준다.

int findAns()
{
	int max = 0;
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (tmpMAP[r][c] == 0) return 0x7fff0000;
			if (max < tmpMAP[r][c]) max = tmpMAP[r][c];
		}
	}

	return max - 1;
}

int MIN = 0x7fff0000;
void DFS(int L, int start)
{
	int tmp;

	if (L > M)
	{
		BFS();
		tmp = findAns();

		if (tmp < MIN) MIN = tmp; /* 최솟값 갱신 */
		return;
	}

	/* ... */
    
}

문제에서 빈칸이 남아있는 경우는, 불가능한 조건이므로, findAns는 최악의 값인 0x7fff0000를 return 한다.

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (50 + 10)

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

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

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

RC virus[MAX*MAX];
int vcnt;

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

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			MAP[r][c] = -1;

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

			if (MAP[r][c] == 1) MAP[r][c] = -1;
			else if (MAP[r][c] == 2)
			{
				virus[vcnt].r = r;
				virus[vcnt++].c = c;

				MAP[r][c] = -2;
			}
		}
	}
}

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

int checkEmpty()
{
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			if (tmpMAP[r][c] == 0) return 1;

	return 0;
}

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

void BFS()
{
	wp = rp = 0;
	for (int r = 0; r <= N + 1; r++)
	{
		for (int c = 0; c <= N + 1; c++)
		{
			tmpMAP[r][c] = MAP[r][c];
			
			if (MAP[r][c] == 1)
			{
				queue[wp].r = r;
				queue[wp++].c = c;
			}
		}
	}

	while (wp > rp)
	{
		RC 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)
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;

				tmpMAP[nr][nc] = tmpMAP[out.r][out.c] + 1;
			}
			else if (tmpMAP[nr][nc] == -2)
			{
				if (checkEmpty())
				{
					queue[wp].r = nr;
					queue[wp++].c = nc;

					tmpMAP[nr][nc] = tmpMAP[out.r][out.c] + 1;
				}
			}
		}
	}
}

int findAns()
{
	int max = 0;
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (tmpMAP[r][c] == 0) return 0x7fff0000;
			if (max < tmpMAP[r][c]) max = tmpMAP[r][c];
		}
	}

	return max - 1;
}

int MIN = 0x7fff0000;
void DFS(int L, int start)
{
	int tmp;

	if (L > M)
	{
		BFS();
		tmp = findAns();

		if (tmp < MIN) MIN = tmp;
		return;
	}

	for (int i = start; i < vcnt; i++)
	{
		MAP[virus[i].r][virus[i].c] = 1;
		DFS(L + 1, i + 1);
		MAP[virus[i].r][virus[i].c] = -2;
	}
}

int main(void)
{
	input();

	DFS(1, 0);

	if (MIN == 0x7fff0000) printf("-1\n");
	else printf("%d\n", MIN);

	return 0;
}

 

실제 A형 문제에서는 tc가 여러 개이므로, 바이러스의 수, vcnt를 초기화하자.