BOJ_14502 / C++

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

14502번: 연구소

백준 온라인저지 14502번 문제입니다. 

브루트포스와 BFS을 이용해서 풀었습니다.

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

enum {
	None,
	Wall,
	Virus
};

int arr[8][8];
int temp[8][8];
int n, m;
int sol;

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

void Input()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++) 
    {
		for (int j = 0; j < m; j++) 
        {
			cin >> arr[i][j];
		}
	}
}

void Copy(int(*a)[8], int(*b)[8]) 
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			a[i][j] = b[i][j];
	}
}


void BFS() {
	
	int bfs[8][8];
	Copy(bfs, temp);
	queue<pair<int, int>> q;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (bfs[i][j] == Virus)
				q.push({ i, j });

	while (!q.empty()) {
		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)
					continue;
			if (bfs[nx][ny] == None)
			{
				bfs[nx][ny] = Virus;
				q.push({ nx, ny });
			}
			
		}
	}
	int cnt = 0;
	for (int i = 0; i < n; i++) 
	{
		for (int j = 0; j < m; j++) 
		{
			if (bfs[i][j] == None)
				cnt += 1;
		}
	}
	sol = max(sol, cnt);
}


void OnWall(int cnt) {
	if (cnt == 3) 
	{
		BFS();
		return;
	}
	for (int i = 0; i < n; i++) 
	{
		for (int j = 0; j < m; j++) 
		{
			if (temp[i][j] == None) 
			{
				temp[i][j] = Wall;
				OnWall(cnt + 1);
				temp[i][j] = None;
			}
		}
	}
}

void solution()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (arr[i][j] == 0)
			{
				Copy(temp, arr);
				temp[i][j] = Wall;
				OnWall(1);
				temp[i][j] = None;
			}
		}
	}
}

int main(void) {
	Input();
	solution();
	cout << sol;
	return 0;
}

아이디어

재귀를 이용해서 먼저 벽을 3개를 세우고 BFS를 이용해서 바이러스에 감염되지 않은 공간을 찾는 방식을 사용했다.

기존의 연구소 상태와 3개의 벽을 세웟을때의 케이스를 확인하는 것, 바이러스가 퍼졌을때 배열이 곂치지 않게 새롭게 복사를 해주는게 포인트라는 생각이 든다. 그리고 가끔 다른 사람들의 코드와 비교해보기 위해 돌아다니다 보니 enum 을 사용하는 분들도 있던데 코드에 가독성이 많이 좋았던 기억이 나서 사용했다.