[C/C++] 백준 - 14502 (연구소)

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

14502번: 연구소

bfs와 백트래킹을 같이 사용하는 문제이지만 내가 듣는 바킹독 알고리즘 분께서는 시물레이션 파트에 넣으셔서

시물레이션 카테고리에 작성하는 문제이다.

 

연구소에 벽을 3개 세운 후 바이러스를 퍼지게 할 때 안전구역의 최대 개수를 구하는 문제이다.

벽을 세울 수 있는 공간일 때 벽을 세우고 다음으로 넘어가 또 세운다. 

벽의 개수가 3개가 되면 바이러스를 퍼지게 한 후 안전구역의 개수를 세어준다.

이때마다 값을 비교해 결국 최대값이 나오게 만들면 된다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<queue>
#define sz 8

using namespace std;

int copy_map[sz][sz];
int map[sz][sz];

int N, M, result;

queue<pair<int, int>> q;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

void Copy_map() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			copy_map[i][j] = map[i][j];
		}	
	}
}

void bfs_virus() {
	int nextX, nextY;

	while (!q.empty()) {
		
		int cur_x = q.front().first;
		int cur_y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			nextX = cur_x + dx[i];
			nextY = cur_y + dy[i];

			if (0 <= nextX && nextX < N && 0 <= nextY && nextY < M) {
				if (copy_map[nextX][nextY] == 0) {
					q.push({ nextX,nextY });
					copy_map[nextX][nextY] = 2;
				}
			}
		}	
	}
}

void bfs(int depth) {
	if (depth == 3) {
		int cnt = 0;
		Copy_map();
		// 바이러스 퍼지는 함수 생성해야함
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (copy_map[i][j] == 2) {
					q.push({ i,j });
				}
			}
		}
		
		bfs_virus();
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (copy_map[i][j] == 0) {
					cnt++;
				}
			}
		}
		result = max(cnt, result);

		return;
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 0) {
				map[i][j] = 1;
				bfs(depth + 1);
				map[i][j] = 0;
			}
		}
	}
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}

	bfs(0);

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

	return 0;
}