백준 14502번 연구소

14502번: 연구소

 

구조는 간단하지만 상당히 까다로웠던 문제.

 

문제는 크게 두 부분으로 나뉜다.

 

1. 연구소의 벽 세우기

2. 바이러스 퍼뜨리기

 

처음에 문제를 접했을 때 완전탐색(브루트포스)를 숙지하지 않았기 때문에 벽을 어떻게 세워야할지에서부터

 

막혔었다. 3중 for문을 생각했지만 택도 없었다.

 

백준 N과 M 문제집을 전부 풀고 나서 완전탐색에 관한 감을 잡았다.

 

벽을 세운 이후에는 BFS를 이용하여 인접 좌표들에 바이러스를 퍼뜨린 결과를 counting하면 끝.

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

int N, M, cnt;
vector<int> arr[9];
vector<int> temp_vec[9];
int temp[9][9];
bool visited[9][9];
queue<pair<int,int>> que;
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
vector<pair<int, int>> vir_vec;
vector<int> result;
bool vist_arr[9][9];

void print() {
	
	cout << '\n';
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cout << arr[i][j] << " ";
		}
		cout << '\n';
	}
	/*
	cout << '\n';
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cout << temp_vec[i][j]<<" ";
		}
		cout << '\n';
	}
	*/
}

void bfs() {
	for (int i = 0; i < 9; i++) {
		memset(visited[i], false, sizeof(visited[i]));
	}
	for(int i = 0; i < vir_vec.size(); i++) {
		que.push(make_pair(vir_vec[i].first, vir_vec[i].second));
		visited[vir_vec[i].first][vir_vec[i].second] = true;

		while (!que.empty()) {
			int x = que.front().first; int y = que.front().second;
			que.pop();
			for (int j = 0; j < 4; j++) {
				int dir_x = x + dir[j][0]; int dir_y = y + dir[j][1];
				if (0 <= dir_x && dir_x < N && 0 <= dir_y && dir_y < M) {
					if (arr[dir_x][dir_y] == 0 && !visited[dir_x][dir_y]) {
						visited[dir_x][dir_y] = true;
						que.push(make_pair(dir_x, dir_y));
						arr[dir_x][dir_y] = 2;
					}
				}
			}
		}
	}
}

void func(int cnt) {
	if (cnt == 3) {
		int temp = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				temp_vec[i][j] = arr[i][j];
			}
		}

		bfs();//바이러스 퍼뜨리기

		for (int i = 0; i < N; i++){//안전구역 count하기
			for (int j = 0; j < M; j++) {
				if (arr[i][j] == 0) {
					temp++;
				}
			}
		}
		result.push_back(temp);

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				arr[i][j] = temp_vec[i][j];
			}
		}
		return;
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (arr[i][j] == 0 ){
				arr[i][j] = 1;
				func(cnt + 1);
				arr[i][j] = 0;//한번 끝내고 나면 arr를 다시 원래대로 돌려줘야 한다. 
			}
		}
	}
}
int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			int temp;
			cin >> temp; arr[i].push_back(temp);
			if (temp == 2) {
				vir_vec.push_back(make_pair(i,j));
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			temp_vec[i].push_back(arr[i][j]);
		}
	}

	func(0);
	
	sort(result.begin(), result.end());

	cout << result.back();

	return 0;
}

 

참고자료

문제집: N과 M (baekjoon)