DFS 풀어 보기

백준 연구소 문제 

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

1. virus 가 퍼지는걸 인지 후 체크 

2. 이때 3개의 방어막을 세우고 count ( 3개를 세우는 방법은 DFS  로 모두 세워준다)

3. 세울때 마다 DFS 로 각각 n 으로 count  를 추가 

#include <stdio.h>
#include <iostream> 
#include <vector>
#include <cmath>
#include <string>
#include <utility>
#include <set>
#include <queue>
#include <functional>
#include<algorithm>
#include <memory.h>


#pragma warning(disable : 4996)
using namespace std;


long long min_v, max_v;


#define MAX(a,b) a>b ? a:b
#define MIN(a,b) a>b ? b:a




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


bool visited[26][26] = { 0, };
int map[26][26];
int N, M, K;
int ans;




//각각의 virus 를 퍼트리는 함수 
void virus_spread(int x, int y) {
	visited[x][y] = true;


	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];


		if (nx >= 0 && nx < N && ny >= 0 && ny< M && !visited[nx][ny] && map[nx][ny] == 0) {
			virus_spread(nx, ny);
		}
	}
}

//get result 를 체크 하는 함수 //
void get_result(){


	int res = 0;


	for (int i = 0; i < N; i++)
	for (int j = 0; j < M; j++)
	if (map[i][j] == 0 && !visited[i][j]) res++;


	ans = max(res, ans);
}




//dfs 에서 각각을 추가해주는 함수 //.
void dfs(int x, int y, int n){
	//map[x][y] = 1;


	if (n == 3) { // 3개일 경우 
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 2) virus_spread(i, j);
			}
		}


		get_result();
		memset(visited, 0, sizeof(visited));


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

				map[i][j] = 1;
				dfs(i, j, n + 1);
				map[i][j] = 0;				
			}

	}


}

int main() {


	int TC = 1;


	///freopen("input3.txt", "r", stdin);	setbuf(stdout, NULL);  cin >> TC;


	int cnt = 0;


	while (TC--){


		ans = 0;


		cin >> N >> M;


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


		//	dbg_print();




		//for (int i = 0; i < N; i++){
		//	for (int j = 0; j < M; j++){
				//if (map[i][j] == 0)
				dfs(0, 0, 0);
		//	}
	//	}
		cout << ans << endl;
	}
	return 0;
}