백준 14502_연구소

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

14502번: 연구소

해당 문제는 DFS와 BFS를 모두 활용하는 시뮬레이션 문제였다.

먼제 바이러스의 확산에서 나는 상하좌우 한 번씩의 감염이 시작되는 줄 모르고 대각선 까지 전부 계산해서 계속 터지는 문제가 있었다...(문제를 끝까지 잘 읽어보고 푸는 습관을 들여야지 생각은 하는데 잘 안된다...ㅠ)

 

어쨌든 상하좌우 한 번씩의 감염이 일어나고 감염된 바이러스는 다시 상하좌우 한 번씩 감염을 일으킨다 -> BFS

그리고 벽을 하나씩 세워서 총 3개를 세운다 -> DFS

 

즉, DFS로 벽을 하나씩 세워보고 벽이 3개가 되는 순간 

BFS를 통해 감염을 일으켜서 안전한 곳의 개수를 세어본다!

이 때 벽을 세울 때, 벽을 세울 수 있는 위치를 pair<int,int> 를 통해 처리한다.

 

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

vector<pair<int, int>> emp; // 0 위치
vector<pair<int, int>> vir; // 2 위치(바이러스)
vector<bool> check; // 체크 (true 세울곳)
int n, m;
int mp[8][8]; // map
int ans = 0;  // 안전영역
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };

// 비교함수
void bfs(){
	int mpc[8][8];
	int mpcv[8][8]; //visit check
	queue<pair<int, int>> virc;
	// copy
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			mpc[i][j] = mp[i][j];
		}
	for (int i = 0; i < vir.size(); i++)
		virc.push(vir[i]);

	// 빈칸 -> 1 벽세우기
	for (int i = 0; i < check.size(); i++) {
		if (check[i]) {
			int x = emp[i].first, y = emp[i].second; // 세울 위치
			mpc[x][y] = 1; // 세우기
		}
	}

	// 바이러스 전파
	while (!virc.empty()) {
		pair<int, int> p = virc.front(); // 꺼내서
		virc.pop();
		int x = p.first, y = p.second;
		for (int d = 0; d < 4; d++) {
			int nx = x + dx[d], ny = y + dy[d];
			if (nx >= 0 && nx < n && ny >= 0 && ny < m && mpc[nx][ny] != 1) {
				if (!mpc[nx][ny]) {
					mpc[nx][ny] = 2; // 감염
					virc.push(pair<int, int>(nx, ny));
				}
			}
		}
	}

	// 안전한 방 세기
	int cnt = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (mpc[i][j] == 0)
				cnt++;

	if (cnt > ans) 
		ans = cnt;
}


void dfs(int idx) {
	// 3 도달시
	if (idx == 3) {
		// check 함수
		bfs();
		return;
	}

	// 넣을 수 있는곳 넣기
	for (int i = 0; i < check.size(); i++) {
		// 안 갔으면
		if (!check[i]) {
			check[i] = true;
			dfs(idx + 1);
			check[i] = false;
		}
	}
}

int main() {
	// input
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> mp[i][j];
			// 빈 칸
			if (mp[i][j] == 0) {
				emp.push_back(pair<int, int>(i, j));
				check.push_back(false);
			}
			// virus
			else if (mp[i][j] == 2)
				vir.push_back(pair<int, int>(i, j));
		}
	}

	dfs(0);
	cout << ans;
}