[코드트리] 바이러스 백신 (삼성 SW 역량테스트 2019 상반기 오후 2번)

삼성 A형 전체 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/vaccine-for-virus

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

 

바이러스 백신 문제 풀이는 BOJ 17142 : 연구소 3과 같다.

#include <stdio.h>

#define MAX (50 + 10)

int T;
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;

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

int minAnswer;

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;
}

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;
}

void DFS(int L, int start)
{
	int tmp;

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

		if (tmp < minAnswer) minAnswer = 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)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();
		minAnswer = 0x7fff0000;

		DFS(1, 0);

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

	return 0;
}