[BOJ] 14502 연구소

Link

https://www.acmicpc.net/problem/14502

Note

바이러스가 유출 되었을 때 벽 3개를 이용해서 최대한 많은 안전한 공간을 만들어야 하는 문제이다.
BFS와 Brute Force를 동시에 사용 해야 하는 문제

바이러스가 퍼지기 전에 벽을 3개만 더 추가해서 최대한 많은 공간을 확보 해야 한다.
문제를 풀 때 크게 새로 벽을 3개 새우는 단계와 BFS/DFS를 통해 바이러스가 확산하는 경우의 2단계로 나누어야 한다.
따라서 벽을 제외한 안전한공간과 바이러스가 있는 공간을 저장하는 배열 2개가 필요하다.

안전한 공간은 벽을 세우기 위한 용도에 사용되고, 바이러스 공간은 BFS/DFS의 시작점으로 사용한다.

필요한 조건은 다 갖추어 졌다. 문제를 풀어보자

알고리즘

1. 연구소 정보를 받으면서 안전한 공간과 바이러스 공간의 개수와 정보를 저장한다.
2. 안전한 공간중 3칸에 벽을 세우는 과정을 진행한다.
3. 3개의 벽이 세워지면 바이러스 시작지점을 통해 BFS/DFS를 통해 바이러스를 확산 시킨다.
4. 확산이 끝난 후의 연구소 정보중 안전한 공간의 수를 헤아려 최대 안전 공간을 갱신한다.

소스코드

#include <iostream>
#include <string.h>

using namespace std;

struct Point {
	short x;
	short y;

	Point() {}
	Point(short x, short y) : x(x), y(y) {}
};

short board[8][8];
Point virusPoint[64];
Point safetyPoint[64];
int virusCount;
int safetyCount;
const int MAXQ = 500;
Point queue[MAXQ];
int head, tail;
int col, row;
int maxSafety = 0;

const short posX[4] = { 1, 0, -1, 0 };
const short posY[4] = { 0, 1, 0, -1 };

void push(short x, short y) {
	queue[head++ % MAXQ] = Point(x, y);
}

Point pop() {
	return queue[tail++ % MAXQ];
}

bool isEmpty() {
	return head == tail;
}

int calSafetyCount(short b[8][8])
{
	int safetyCount = 0;
	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++)
			if (b[i][j] == 0)
				safetyCount++;
	return safetyCount;
}

void bruteForce(int pos, int latest)
{
	if (pos == 3)
	{
		short tempBoard[8][8];
		bool check[8][8];

		memset(check, false, sizeof(check));

		for (int i = 0; i < 8; i++)
			for (int j = 0; j < 8; j++)
				tempBoard[i][j] = board[i][j];

		for (int i = 0; i < virusCount; i++)
		{
			if (check[virusPoint[i].x][virusPoint[i].y])
				continue;

			push(virusPoint[i].x, virusPoint[i].y);

			while (!isEmpty())
			{
				Point cur = pop();

				if (check[cur.x][cur.y])
					continue;

				check[cur.x][cur.y] = true;

				for (int pos = 0; pos < 4; pos++)
				{
					int nextX = cur.x + posX[pos];
					int nextY = cur.y + posY[pos];

					if (0 <= nextX && nextX < row && 0 <= nextY && nextY < col && tempBoard[nextX][nextY] == 0)
					{
						tempBoard[nextX][nextY] = 2;
						push(nextX, nextY);
					}
				}
			}
		}
		
		int zone = calSafetyCount(tempBoard);

		if (maxSafety < zone)
			maxSafety = zone;
	}
	else
	{
		for (int i = latest; i < safetyCount; i++)
		{
			Point point = safetyPoint[i];
			board[point.x][point.y] = 1;
			bruteForce(pos+1, i + 1);
			board[point.x][point.y] = 0;
		}
	}
}

int main()
{
	cin >> row >> col;

	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++)
		{
			cin >> board[i][j];

			if (board[i][j] == 2)
				virusPoint[virusCount++] = Point(i, j);
			else if (board[i][j] == 0)
				safetyPoint[safetyCount++] = Point(i, j);
		}

	bruteForce(0, 0);

	cout << maxSafety;

	return 0;
}

2019-01-18 20:05:19에 Tistory에서 작성되었습니다.