728x90
https://www.acmicpc.net/problem/14502
//14502 연구소
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int max_val=0;
int n, m;
void bfs(vector<vector<int>> &board){
queue<pair<int, int>> q;
vector<vector<int>> new_board(n, vector<int>(m, 0));
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < m ; j++){
if(board[i][j]==2){
q.push({i, j});
}
new_board[i][j] = board[i][j];
}
}
int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};
while(!q.empty()){
int r = q.front().first;
int c = q.front().second;
q.pop();
for(int i = 0 ; i < 4 ; i++){
int nr = r + dr[i];
int nc = c + dc[i];
if(nr >= n || nr < 0 || nc < 0 || nc >= m){
continue;
}
if(new_board[nr][nc]!=0)
continue;
new_board[nr][nc] = 2;
q.push({nr, nc});
}
}
int count = 0;
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < m ; j++){
if(new_board[i][j]==0)
count++;
}
}
max_val = max(max_val, count);
}
void backtracking(vector<vector<int>> &board, int depth){
if(depth==3){
bfs(board);
return;
}
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < m ; j++){
if(board[i][j]==0){
board[i][j] = 1;
backtracking(board, depth+1);
board[i][j] = 0;
}
}
}
}
int main(){
cin >> n >> m;
vector<vector<int>> board(n, vector<int>(m, 0));
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < m ; j++){
cin >> board[i][j];
}
}
backtracking(board, 0);
cout << max_val;
return 0;
}
백트래킹과 bfs 기본만 알면 어렵지 않은 문제가 아닐까 생각한다.
1. 백트래킹으로 3개의 벽을 세운다.
2. 각 경우의 수마다 bfs로 바이러스를 퍼뜨린 후 안전영역을 센다.
3. 모든 경우의 수 중 최솟값 계산.
'알고리즘' 카테고리의 다른 글
[백준/C++] 톱니바퀴 (0) | 2022.03.25 |
---|---|
[C++/백준 21608] 상어 초등학교 (0) | 2022.03.25 |
[C++/백준 21610] 마법사 상어와 비바라기 (0) | 2022.03.19 |
[C++/백준 19538] 루머 (0) | 2022.03.18 |
[C++/백준 2638] 치즈 (0) | 2022.03.15 |