반응형
#include "pch.h"
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <memory.h>

using namespace std;

int lab[8][8];
int tempLab[8][8];
int n, m;
int ans = 0;

int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

void virusSpread(void)
{
	int SpreadLab[8][8];
	memcpy(SpreadLab, tempLab, sizeof(tempLab));
	queue<pair<int, int>> q;

	/* Map 중 Virus 있는 좌표 저장 */
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (SpreadLab[i][j] == 2)
			{
				q.push(make_pair(i, j));
			}
		}
	}

	while (q.empty() == false)
	{
		int x = q.front().first;
		int y = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) //동서남북으로 체크
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (0 <= nx && nx < n && 0 <= ny && ny < m) //x, y의 인접한 && 유효한 범위 내에서
			{
				if (SpreadLab[nx][ny] == 0) //바이러스가 퍼지지 않았으면
				{
					SpreadLab[nx][ny] = 2; //바이러스 퍼뜨린다.
					q.push(make_pair(nx, ny));
				}
			}
		}
	}

	int cnt = 0;
	/* 바이러스 감염안된 숫자 카운트 */
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (SpreadLab[i][j] == 0)
			{
				cnt++;
			}
		}
	}

	ans = max(ans, cnt);
}

void wall(int cnt)
{
	if (cnt == 3)
	{
		virusSpread();
		return;
	}
	else
	{
		/* 모든 경우의 수에 벽 세우기 */
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (tempLab[i][j] == 0)
				{
					tempLab[i][j] = 1;
					wall(cnt + 1);
					tempLab[i][j] = 0;
				}
			}
		}
	}
}

int main()
{
	scanf_s("%d %d", &n, &m);

	for (int i = 0;i < n;i++)
	{
		for (int j = 0; j < m; j++)
		{
			//scanf("%d", &lab[i][j]);
			scanf_s("%d", &tempLab[i][j]);
		}
	}

	wall(0);

	printf("%d\n", ans);
	return 0;
}
반응형

+ Recent posts