- 방법 1 : 조합을 이용 - > 들어갈 수 있는 위치를 모두 벡터에 저장하고 거기서 3개를 고르는 조합을 만든 후에 벽을 세우고 바이러스를 퍼뜨리고 숫자를 세는 방식
- 방법 2 : for문을 이용하여 3개의 벽을 모두 세우고 모든 조건과 같은 공간에 둔게 아니라면 바이러스를 퍼뜨리고 숫자를 세는 방식
- 공통 : spread의 경우에는 BFS를 이용해서 바이러스를 퍼뜨린다.
#include <iostream>
#include <algorithm>
#include <queue>
#include <limits.h>
using namespace std;
int n,m;
int a[8][8];
int dx[4] = {0,1,0,-1};
int dy[4] = {-1,0,1,0};
int ans = 0;
char tmp_input;
void spread(){
queue<pair<int,int> > q;
// 초반에 2가 있는 위치들을 큐에 추가
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(a[i][j] == 2){
q.push(make_pair(i,j));
}
}
}
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
for(int k=0; k<4; k++){
int nx = x + dx[k];
int ny = y + dy[k];
// 범위 안에 있고
if(nx >=0 && ny >=0 && nx < n && ny < m){
// 0이라면
if(a[nx][ny] == 0){
a[nx][ny] = 2;
q.push(make_pair(nx,ny));
}
}
}
}
}
void count_and_get_max(){
int cnt = 0;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(a[i][j] == 0){
cnt++;
}
}
}
ans = (ans<cnt) ? cnt : ans;
}
void print_map(){
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cout << a[i][j] << ' ';
}
cout << '\n';
}
cout << '\n';
}
int main(){
cin >> n >> m;
vector<pair<int,int> > points;
vector<int> comb;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin >> a[i][j];
if(a[i][j] == 0){
points.push_back(make_pair(i,j));
}
}
}
//0을 채우고 1을 채움
for(int i=0; i<points.size()-3; i++){
comb.push_back(0);
}
for(int i=0; i<3; i++){
comb.push_back(1);
}
do{
int tmp[8][8];
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
tmp[i][j] = a[i][j];
}
}
for(int i=0;i<comb.size();i++){
if(comb[i] == 1){
a[points[i].first][points[i].second] = 1;
}
}
spread();
count_and_get_max();
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
a[i][j] = tmp[i][j];
}
}
}while(next_permutation(comb.begin(),comb.end()));
cout << ans << '\n';
return 0;
}
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int a[8][8];
int n,m;
int ans = 0;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int bfs(){
int tmp[8][8];
queue<pair<int,int> > q;
// 현재 정보들 저장
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
tmp[i][j] = a[i][j];
}
}
// 2의 위치들 큐에 넣기
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(a[i][j] == 2){
q.push(make_pair(i,j));
}
}
}
// spread
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
for(int k=0; k<4; k++){
int nx = x + dx[k];
int ny = y + dy[k];
if(nx >=0 && nx<n && ny>=0 && ny<m){
if(a[nx][ny] == 0){
a[nx][ny] = 2;
q.push(make_pair(nx,ny));
}
}
}
}
// 0들 세어보기
int cnt = 0;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(a[i][j] == 0){
cnt++;
}
}
}
// 정보들 되돌리기
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
a[i][j] = tmp[i][j];
}
}
return cnt;
}
int main(){
cin >> n >> m;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin >> a[i][j];
}
}
for(int x1=0; x1<n; x1++){
for(int y1=0; y1<m; y1++){
if(a[x1][y1] != 0) continue;
for(int x2=0; x2<n; x2++){
for(int y2=0; y2<m; y2++){
if(a[x2][y2] != 0) continue;
for(int x3=0; x3<n; x3++){
for(int y3=0; y3<m; y3++){
if(a[x3][y3] != 0) continue;
if(x1==x2 && y1==y2)continue;
if(x2==x3 && y2==y3)continue;
if(x3==x1 && y3==y1)continue;
a[x1][y1] = 1;
a[x2][y2] = 1;
a[x3][y3] = 1;
int cur = bfs();
ans = (ans < cur) ? cur : ans;
a[x1][y1] = 0;
a[x2][y2] = 0;
a[x3][y3] = 0;
}
}
}
}
}
}
cout << ans << '\n';
return 0;
}
- DFS로 풀려고 했으나 풀리지 않아서 for문을 이용하는 방법과 조합을 이용하는 방법을 이용해서 풀었다
- 생각보다 시간이 짧게 나와서 나쁘지 않은 풀이 같다. 결국 돌아가는 데이터의 크기가 작다면 (대략 1억번에 1초임을 감안) 조합이나 for문도 나쁘지 않은 선택이다.