[BOJ] #14502 _ 연구소

[연구소] https://www.acmicpc.net/problem/14502

14502번: 연구소

N과 M의 최대 값이 8로 별로 크지 않고,

벽을 세우는 특정한 조건이 주어져있지 않다.

따라서, 벽을 세울 수 있는 모든 경우의 수를 고려하는 브루트포스 문제라고 생각하였다.

 

BFS (Breadth-First Search)
너비 우선 탐색은 임의의 노드의 인접한 노드를 먼저 탐색하는 방법

DFS (Depth-First Search)
깊이 우선 탐색은 임의의 노드에서 다음 분기로 넘어가기 전 해당 분기를 완벽히 탐색하는 방법

 

바이러스를 퍼트리는 방법으로는 DFS나 BFS 알고리즘을 사용할 수 있다.

나는 BFS를 사용하였다.

 

[ 소스 코드 ]

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#define MAX 9

using namespace std;

int dx[] = { 0,0,-1,1 }, dy[] = { -1,1,0,0 };
int n, m, result;
int map[MAX][MAX], tmp_map[MAX][MAX];
vector<pair<int, int> > virus;

void solve(int cnt, int y, int x);
void spreadVirus();
int cntSecuritySpace();
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 2) virus.push_back(make_pair(i, j));
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (map[i][j] != 0) continue;
			map[i][j] = 1;
			solve(1, i, j);
			map[i][j] = 0;
		}
	}
	printf("%d\n", result);

	return 0;
}

void solve(int cnt, int y, int x) {
	if (cnt >= 3) {
		spreadVirus();
		result = max(result, cntSecuritySpace());
		return;
	}

	for (int i = y; i <= n; i++) {
		for (int j = x; j <= m; j++) {
			if (map[i][j] != 0) continue;
			map[i][j] = 1;
			solve(cnt + 1, i, j);
			map[i][j] = 0;
		}
		x = 1;
	}
}

void spreadVirus() {
	memcpy(tmp_map, map, sizeof(map));

	for (int i = 0; i < virus.size(); i++) {
		queue<pair<int, int> > tmp;
		tmp.push(virus[i]);

		while (!tmp.empty()) {
			int x = tmp.front().second, y = tmp.front().first;
			tmp.pop();
			for (int j = 0; j < 4; j++) {
				int tmp_x = x + dx[j], tmp_y = y + dy[j];

				if (tmp_x<1 || tmp_y<1 || tmp_x>m || tmp_y>n) continue;
				if (tmp_map[tmp_y][tmp_x] != 0) continue;

				tmp_map[tmp_y][tmp_x] = 2;
				tmp.push(make_pair(tmp_y, tmp_x));
			}
		}
	}
}

int cntSecuritySpace() {
	int cnt = 0;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (tmp_map[i][j] == 0) cnt++;
		}
	}

	return cnt;
}