728x90
반응형


이 문제는 삼성 SW 기출문제이고, brute force와 bfs를 사용하여 풀었다.
연구소에 3개의 벽을 세워 모든 경우의 수를 따진 후(brute force),
bfs로 바이러스를 추적한 뒤, 빈칸의 개수를 구하여 이 문제를 해결할 수 있었다.
void combination(int depth){
if(depth == 3){
bfs();
initVisited();
int count = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(area[i][j] == 0){
count++;
}
if(area[i][j] == 3){
area[i][j] = 0;
}
}
}
maxNum = max(maxNum, count);
return;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (area[i][j] == 0) {
area[i][j] = 1;
combination(depth + 1);
area[i][j] = 0;
}
}
}
}
완성된 코드는 이러하다.
//연구소
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;
bool visited[8][8];
int area[8][8];
int directx[]= {0,0,1,-1};
int directy[] = {1,-1,0,0};
int maxNum = 0, n, m;
vector<int> safetyAreaVector;
void initVisited(){
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
visited[i][j] = false;
}
}
}
void bfs(){
queue<pair<int,int>> q;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(area[i][j] == 2){
visited[i][j] = true;
q.push({i,j});
}
}
}
while(!q.empty()){
pair<int,int> node = q.front();
q.pop();
for(int i = 0; i < 4; i++){
int dx = node.first + directx[i];
int dy = node.second + directy[i];
if(dx >= 0 && dy >= 0 && dx < n && dy < m && visited[dx][dy] == false && area[dx][dy] == 0){
area[dx][dy] = 3;
visited[dx][dy] = true;
q.push({dx,dy});
}
}
}
}
void combination(int depth){
if(depth == 3){
bfs();
initVisited();
int count = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(area[i][j] == 0){
count++;
}
if(area[i][j] == 3){
area[i][j] = 0;
}
}
}
maxNum = max(maxNum, count);
return;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (area[i][j] == 0) {
area[i][j] = 1;
combination(depth + 1);
area[i][j] = 0;
}
}
}
}
int main(void){
cin >> n >> m;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> area[i][j];
}
}
combination(0);
cout << maxNum;
}
반응형
'algorithm' 카테고리의 다른 글
[algorithm] 백준 - 감시 (0) | 2020.12.24 |
---|---|
[algorithm] 백준 - 톱니바퀴 (0) | 2020.12.24 |
[algorithm] 백준 - 경사로 (0) | 2020.12.23 |
[algorithm] 백준 - 연산자 끼워넣기 (0) | 2020.12.22 |
[algorithm] 백준 - 로봇 청소기 (0) | 2020.12.22 |