[백준알고리즘] 14502 연구소 RE1

연구소 RE1

 

#include <stdio.h>

 

//dfs로 벽세우기
//맵 저장해놓고 bfs로 바이러스 뿌린뒤 맵 복구

int N, M, cnt, result;
int map[8][8];
bool visit[8][8];
bool visit2[8][8];
int tmp[8][8];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
typedef struct info
{
 int x, y;
};

void pnt()
{
 printf("\n");
 for (int i = 0; i < N; i++)
 {
  for (int j = 0; j < M; j++)
   printf("%d ", visit[i][j]);
  printf("\n");
 }

 printf("\n--------------\n");
}

void recovery()
{
 for (int i = 0; i < N; i++)
  for (int j = 0; j < M; j++)
   map[i][j] = tmp[i][j];
 return;
}

void copy()
{
 for (int i = 0; i < N; i++)
  for (int j = 0; j < M; j++)
   tmp[i][j] = map[i][j];
 return;
}

void bfs(int x, int y)
{
 info q[64];
 int front = 0, rear = 0;
 q[rear] = { x,y };
 rear++;

 while (front != rear)
 {
  info cur = q[front];
  front++;

  for (int k = 0; k < 4; k++)
  {
   int nx = cur.x + dx[k];
   int ny = cur.y + dy[k];
   
   if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;

   if (map[nx][ny] == 1 || map[nx][ny] == 2) continue;

   if (visit2[nx][ny]) continue;

   map[nx][ny] = 2;
   visit2[nx][ny] = true;
   q[rear] = { nx,ny };
   rear++;
  }
 }

 for (int i = 0; i < rear; i++)
  q[i] = { 0,0 };

 return;
}

void initvisit()
{
 for (int i = 0; i < N; i++)
  for (int j = 0; j < M; j++)
   visit2[i][j] = false;
 return;
}

void dfs(int x, int y, int num)
{
 if (num == 3)
 { //pnt();

  copy();
  initvisit();

  for(int i=0;i<N;i++)
   for(int j=0;j<M;j++)
   {
    if (map[i][j] == 2)
     bfs(i, j);
    }
  
  cnt = 0;

  for (int i = 0; i < N; i++)
   for (int j = 0; j < M; j++)
    if (map[i][j] == 0) cnt++;

  if (result < cnt) result = cnt;

  recovery();

  return;
 }

 for (int i = 0; i < N; i++)
  for (int j = 0; j < M; j++)
  {
   if (map[i][j] == 2 || map[i][j] == 1
    || visit[i][j]) continue;

   visit[i][j] = true;
   map[i][j] = 1;
   dfs(i, j, num + 1);
   map[i][j] = 0;
   visit[i][j] = false;
  }
 return;
}

int main()
{
 scanf("%d%d", &N, &M);

 for (int i = 0; i < N; i++)
  for (int j = 0; j < M; j++)
   scanf("%d", &map[i][j]);

 result = 0;

 dfs(0, 0, 0);

 printf("%d\n", result);

 return 0;
}