[백준 14502번] 연구소 C++

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

풀이 방법

약간 BFS를 이용하여 주먹구구식으로 문제를 풀어보았다.
6중 for문으로 벽을 3개 세우고, 3개가 세워지는 시점에 BFS 알고리즘을 통해 바이러스를 퍼뜨린다. 그 이후 남은 안전지대의 개수를 세는 방법으로 접근했다. 6중 for문이라서 당연히 시간초과가 뜰거라 생각했지만 시간이 넉넉하게 주어져서 통과했다.

벽을 세울 후보지를 조합으로 3곳을 정하여 풀면 더 빠른 시간 안에 풀 수 있을 것 같다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>  // pair
#include <tuple>
#include <stack>
#define ll long long
#define INF 1e9
using namespace std;

int n,m;
int mxN = 0;
int map[9][9];
int dr[] = {0,1,0,-1};
int dc[] = {1,0,-1,0};
bool visited[9][9];
vector<int> originR;
vector<int> originC;

void bfs() {
	queue< pair<int,int> > q;

	for(int i=0;i<originR.size();++i) {
		q.push(make_pair(originR[i], originC[i]));
	}

	int newmap[9][9];
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j) {
			newmap[i][j] = map[i][j];
		}
	}

	while(!q.empty()) {
		pair<int,int> p = q.front();
		q.pop();

		int r = p.first;
		int c = p.second;

		for(int i=0;i<4;++i) {
			int nr,nc;
			nr = r + dr[i];
			nc = c + dc[i];

			if(nr < 1 || nr > n || nc < 1 || nc > m) {
				continue;
			} else {
				if(newmap[nr][nc] == 0) {
					newmap[nr][nc] = 2;
					q.push(make_pair(nr, nc));
				}
			}
		}
	}

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

	mxN = max(mxN, cnt);

	return;
	
}

void sol() {
	for(int a=1;a<=n;++a) {
		for(int b=1;b<=m;++b) {
			if(map[a][b] == 0 && !visited[a][b]) {
				map[a][b] = 1;
				visited[a][b] = true;
			}
			else continue;

			for(int c=1;c<=n;++c) {
				for(int d=1;d<=m;++d) {
					if(map[c][d] == 0 && !visited[c][d]) {
						map[c][d] = 1;
						visited[c][d] = true;
					}
					else continue;

					for(int e=1;e<=n;++e) {
						for(int f=1;f<=m;++f) {
							if(map[e][f] == 0 && !visited[e][f]) {
								map[e][f] = 1;
								visited[e][f] = true;
							}
							else continue;

							bfs();
							map[e][f] = 0;
							visited[e][f] = false;
						}
					}

					map[c][d] = 0;
					visited[c][d] = false;
				}
			}

			map[a][b] = 0;
			visited[a][b] = false;
		}
	}
}

int main(void) {
	ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);


	cin >> n >> m;

	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j) {
			cin >> map[i][j];
			if(map[i][j] == 2) {
				originR.push_back(i);
				originC.push_back(j);
			}
		}
	}

	sol();

	cout << mxN << '\n';
	
	return 0;
}