백준 14502_연구소(C++)

 

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

14502번: 연구소

[문제 풀이]

시뮬레이션을 이용하여 문제를 풀었습니다.

 

시뮬레이션을 구현하는 과정에서 BFS와 조합이 쓰였습니다. 이 문제의 경우 연구소를 2차원 배열의 형태로 주고 벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라 하고, 안전 영역의 최대값을 구하는 문제였습니다.

 

먼저 벽 3개를 세우기 위해 조합을 이용하여 3개의 벽을 세울 수 있는 모든 경우를 찾은 후 BFS를 이용하여 바이러스를 퍼뜨려 주었습니다. 퍼뜨릴 때마다 영역의 값을 구한 후 최대인 경우를 찾았습니다.

[코드]

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

int N, M;
int result = 0;

queue<pair<int, int>> que;
vector<pair<int, int>> virus;

int map[8][8];
int check[8][8];
int visit[8][8] = { 0, };
int dx[4] = { -1, 0, 1 ,0 };
int dy[4] = { 0, 1 , 0, -1 };

void combination(int, int, int);
void bfs();
void mapCopy();
void insertQueue();
void score();

int main() {

	scanf("%d %d", &N, &M);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			int temp;
			scanf("%d", &temp);

			map[i][j] = temp;

			if (temp == 2)
				virus.push_back(make_pair(i, j));
		}
	}


	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {

			if (map[i][j] == 0) {
				map[i][j] = 1;
				combination(i, j, 1);
				map[i][j] = 0;
			}
		}
	}

	printf("%d\n", result);

}

void combination(int idx, int jdx, int cnt) {

	if (cnt == 3) {

		insertQueue();
		mapCopy();
		bfs();
		return;
	}


	for (int i = idx; i < N; i++) {
		for(int j = 0; j < M; j++){

			if (map[i][j] == 0) {
				map[i][j] = 1;
				combination(i, j, cnt + 1);
				map[i][j] = 0;
			}

		}
	}

}

void insertQueue() {

	for (int i = 0; i < virus.size(); i++)
		que.push(make_pair(virus[i].first, virus[i].second));

}

void score() {

	int temp = 0;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (check[i][j] == 0)
				temp++;
		}
	}

	if (temp > result)
		result = temp;
}

void mapCopy() {

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)			
			check[i][j] = map[i][j];

}

void bfs() {

	for (int i = 0; i < N; i++) 
		for (int j = 0; j < M; j++)
			visit[i][j] = 0;


	while (!que.empty()) {

		int x = que.front().first;
		int y = que.front().second;

		visit[x][y] = 1;

		for (int i = 0; i < 4; i++) {

			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || ny < 0 || nx >= N || ny >= M || visit[nx][ny] == 1 || check[nx][ny] == 1 || check[nx][ny] == 2)
				continue;

			check[nx][ny] = 2;
			visit[nx][ny] = 1;
			que.push(make_pair(nx, ny));
		}

		que.pop();
	}

	score();

}