[백준14502]연구소

1)문제분류

-DFS

-BFS

2)해결방안

 -기본 DFS와 BFS를 안다면 풀 수 있는 난이도?

 - 먼저 DFS로 3개의 막대를 세워보며 BFS로바이러스를 퍼뜨린다.

 - 그 후, 안전지대를 카운트 세며 크기비교하면, 가장 넓은영역을 알 수 있다.

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cstring>

using namespace std;

typedef struct v

{

int x, y;

}v;

queue<v>virous;

int map[10][10];

int xrr[4] = { 0,0,1,-1 };

int yrr[4] = { 1,-1,0,0 };

int n, m, hap;

int ans = 0;//안전영역

int BFS()

{

queue<v>temp;

temp = virous;

int chk[10][10] = { 0, };

int copy[10][10];

for (int i = 0; i < n; i++)

{

for (int j = 0; j < m; j++)

{

copy[i][j] = map[i][j];

}

}

int cnt = virous.size(); //바이러스 개수

while (!temp.empty()) //퍼진다앙

{

v output = temp.front();

temp.pop();

for (int i = 0; i < 4; i++)

{

int inputx = output.x+xrr[i];

int inputy = output.y+yrr[i];

if (inputx<0 || inputy<0 || inputx>n - 1 || inputy>m - 1|| copy[inputx][inputy]!=0)continue;

if (chk[inputx][inputy] == true)continue;

copy[inputx][inputy]= 2;

chk[inputx][inputy] == true;

cnt++;

temp.push({ inputx,inputy });

}

}

return hap - cnt; //전체에서 바이러스개수 빼주기

}

void dfs(int x,int y,int cnt)

{

if (cnt == 3)

{

ans=max(ans,BFS());

return;

}

for (int i = x ; i < n; i++)

{

for (int j = 0; j < m; j++)

{

if (map[i][j] == 0)

{

map[i][j] = 1;

dfs(i,j,cnt+1);

map[i][j] = 0;

}

}

}

}

int main()

{

cin >> n >> m;

int stick=0;

for (int i = 0; i < n; i++)

{

for (int j = 0; j < m; j++)

{

cin >> map[i][j];

if (map[i][j] == 2)

virous.push({ i,j });

else if (map[i][j] == 1)stick++;

}

}

hap = n * m - 3-stick; //-3막대 -stick은 1

dfs(0, 0, 0);

cout << ans << endl;

}