for문을 이렇게 많이 써본건 처음이야…

문제

  • 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

2 1 0 0 1 1 0 1 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

2 1 0 0 1 1 2 1 0 1 0 1 2 2 0 1 1 0 1 2 2 0 1 0 0 0 1 2 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력

  • 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

출력

  • 첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

예제

예제 입력
7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

예제 출력
27

예제 입력
4 6
0 0 0 0 0 0
1 0 0 0 0 2
1 1 1 0 0 2
0 0 0 0 0 2

예제 출력
9

예제 입력
8 8
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

예제 출력
3

접근

  • 2019년 여름방학 당시 이 문제를 처음 보았다. 처음 봤을 때 머리속에 떠오르는 생각은 6중 for문밖에 없었다…
  • 2019년 11월 이 문제를 다시 보았다. 머리속에 떠오르는 방법은 6중 for문밖에 없었다…
    • 그 당시엔 시간 복잡도를 계산하지 않아 에이 6중 for문은 아니겠지 하면서 넘겼지만 시간 복잡도를 계산해보니 6중 for문으로 해결할 수 있겠다는 생각이 들었다…
  • 벽 3개를 세운 후 BFS를 진행시키는 쪽으로 구상했다.

내가 생각한 풀이

  • 접근과 같다. 6중 for문을 돌아가며 벽을 세울 수 있는 모든 경우의 수를 찾아준다.
    • 이 때 벽이 겹치거나 이미 무언가 존재하는 곳에 세워지지 않게끔 조건을 걸어준다.
  • 벽의 경우의 수마다 BFS를 실행하여 최대값을 갱신시킨다.

코드

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

int N,M,map[8][8] = {0, },tmap[8][8] = {0, }, d[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}, r = 0;

queue<struct xy> q;
vector<struct xy> v;
struct xy{
  int y;
  int x;
};
bool chk(int a, int b){return (a>=0 && b>=0 && a<N && b<M);}
void doBFS(){
  int count = 0;
  for(int i = 0 ;i<v.size();i++) q.push({v[i].y,v[i].x});
  while(!q.empty()){
    struct xy t = q.front();
    q.pop();
    for(int i = 0 ;i<4;i++){
      if(chk(t.y + d[i][0], t.x + d[i][1]) && tmap[t.y + d[i][0]][t.x + d[i][1]] == 0){
        q.push({t.y + d[i][0], t.x + d[i][1]});
        tmap[t.y + d[i][0]][t.x + d[i][1]] = 2;
      }
    }
  }
  for(int i = 0 ;i<N;i++){
    for(int j = 0 ;j<M;j++){
      if(tmap[i][j] == 0) count++;
    }
  }
  if(count>r) r = count;
}
int main(void){
  cin>>N>>M;
  int zerocount = 0;
  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});
      if(map[i][j] == 0) zerocount++;
    }
  }
  if(zerocount == 3){ //빈 공간이 3개, 즉 벽을 세울 수 있는 공간이 3개밖에 없으면 0 출력
    cout<<0;
    return 0;
  }
  for(int a = 0 ; a<N ; a++){
    for(int b = 0 ; b<M ; b++){
      for(int c = 0 ; c<N ; c++){
        for(int d = 0 ; d<M ; d++){
          for(int e = 0 ; e<N ; e++){
            for(int f = 0 ; f<M ; f++){
              for(int i = 0 ;i<N;i++){
                for(int j = 0 ;j<M;j++) tmap[i][j] = map[i][j]; //매번 복제맵을 만들어준다.
              }
              if((a==c && b==d) || (a==e && b==f) || (c==e && d==f)){ //벽이 겹치지 않게 세워야 하므로 다음 조건을 넣어준다.
                  continue;
              }
              else if(tmap[a][b] == 2 || tmap[c][d] == 2 || tmap[e][f] == 2 || tmap[a][b] == 1 || tmap[c][d] == 1 || tmap[e][f] == 1) continue; //이미 뭔가가 있는 곳에는 벽을 세울 수 없으므로 다음 조건을 넣어준다.
              else{
                tmap[a][b] = 1; tmap[c][d] = 1; tmap[e][f] = 1;
                doBFS();
              }
            }
          }
        }
      }
    }
  }
  cout<<r;
  return 0;
}