[BOJ 14502] 연구소

https://www.acmicpc.net/problem/14502

1. input 값을 받으며 2의 개수 및 좌표와 0의 개수를 저장한다.

2. dfs로 전체를 돌며 0인 곳에 3개씩 1로 만든다.

3. 3개를 만들고 나면 2의 좌표를 돌며 바이러스를 퍼트리면서 안전영역을 구한다.

4. dfs가 끝나면 result에 안전영역 최댓값이 들어있으므로 출력한다.

#include <iostream>

#include <algorithm>

#include <memory.h>

using namespace std;

int N, M, cnt0, cnt2, tmp, result;

int map[8][8];

int v[64][2];

bool visited[8][8];

bool calvisited[8][8];

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

void cal(int i, int j)

{

calvisited[i][j] = true;

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

{

int nexti = i + dir[d][0]; int nextj = j + dir[d][1];

if (nexti >= 0 && nextj >= 0 && nexti < N && nextj < M

&& !calvisited[nexti][nextj] && map[nexti][nextj] ==0)

{

tmp--;

cal(nexti, nextj);

}

}

}

void dfs(int t)

{

if (t == 0)

{

tmp = cnt0-3;

memset(calvisited, false, sizeof(calvisited));

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

{

cal(v[i][0], v[i][1]);

}

result = max(result, tmp);

return;

}

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

{

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

{

if (map[i][j] == 0 && !visited[i][j])

{

map[i][j] = 1; visited[i][j] = true;

dfs(t-1);

map[i][j] = 0; visited[i][j] = false;

}

}

}

}

int main()

{

cin >> N >> M; cnt0 = 0; cnt2 = 0; result = 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[cnt2][0] = i; v[cnt2][1] = j;

cnt2++;

}

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

{

cnt0++;

}

}

}

dfs(3);

cout << result << endl;

return 0;

}