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

www.acmicpc.net/problem/14502

14502번: 연구소

삼성 역량 테스트 기출 문제 : DFS + BFS

 

벽을 3개씩 세우는 모든 경우의 수는 DFS를 통해 구현하고, 이렇게 세워진 벽에서 바이러스가 퍼져나갔을 때 안전영역의 최대 개수는 BFS를 통해 구하도록 구현하였습니다.

 

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

int n, m, answer;
int map[9][9];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
vector<pair<int, int > > v, b;

int BFS() {
	int copyMap[9][9];
	memcpy(copyMap, map, sizeof(map));
	queue<pair<int, int > > q;
	
	for(int i = 0; i < v.size(); i++) {
		q.push(v[i]);
	}
	
	while(!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(copyMap[nx][ny] != 0 || nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			copyMap[nx][ny] = 2;
			q.push({ nx, ny });
		}
	}
	
	// 안전 영역 구하기 
	int area = 0;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(copyMap[i][j] == 0) area++;
		}
	}
	
	return area;
}

void DFS(int cnt) {
	if(cnt == 3) { // 벽이 3개 세워지면 BFS 작동 
		answer = max(answer, BFS());
		return;
	}
	
	for(int i = 0; i < b.size(); i++) {
		int x = b[i].first;
		int y = b[i].second;
		if(map[x][y] == 0) {
			map[x][y] = 1;
			DFS(cnt + 1);
			map[x][y] = 0;
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cin >> map[i][j];
			if(map[i][j] == 2) v.push_back({ i, j }); // 바이러스 좌표 저장
			else if(map[i][j] == 0) b.push_back({ i, j }); // 빈칸 좌표 저장
		}
	}
	
	DFS(0);
	cout << answer;
}