백준(BOJ) 14502번 연구소 *

오랜만에 시작한 알고리즘 첫 문제~

1. 배열의 크기가 작다보니 모든 3개의 벽을 놓는 모든 경우의 수를 확인
2. DFS를 이용하여 바이러스를 퍼지게 한다.
3. 안전한 공간의 개수를 확인한다.

실수 했던 부분
3개의 벽은 반드시 놓아야 한다.
즉, 바이러스가 없는 경우에도 3개의 벽은 놓아야한다.(80퍼 쯤에서 에러 발생)

* : 기본적인 DFS 이고 모든 경우의 수를 확인 하면 된다는 점에서 쉽게 풀 수 있을것 같다.

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int map[10][10],ori[10][10],x,y,mx=0,tmp=0,dx[4] = { -1,0,1,0 },dy[4] = { 0,-1,0,1 };
void dfs(int y, int x)
{
	for(int i=0;i<4;i++)
		if (map[y + dy[i]][x + dx[i]] == 0)
		{
			map[y + dy[i]][x + dx[i]] = 2;
			dfs(y + dy[i], x + dx[i]);
		}
}
int main()
{
	fill_n(&ori[0][0], 10 * 10, 1);
	scanf("%d%d",&y,&x);
	for (int i = 1; i <= y; i++)
		for (int k = 1; k <= x; k++)
			scanf("%d", &ori[i][k]);
	for(int i=0;i<x*y;i++)
		for (int k = i+1; k < x*y; k++)
			for (int p = k+1; p < x*y; p++)
				if (ori[i / x + 1][i%x + 1] == 0 && ori[k / x + 1][k%x + 1] == 0 && ori[p / x + 1][p%x + 1] == 0)
				{
					tmp = 0;
					memcpy(map, ori, sizeof(int)*10*10);
					map[i / x + 1][i%x + 1] = 1;	
					map[k / x + 1][k%x + 1] = 1;
					map[p / x + 1][p%x + 1] = 1;
					for (int q = 0; q <= x*y; q++)
						if (map[q / x + 1][q%x + 1] == 2)
							dfs(q / x + 1, q%x + 1);
					for (int q = 0; q < x*y; q++)
						if (map[q / x + 1][q%x + 1] == 0)
							tmp++;
					if (mx < tmp)
						mx = tmp;
				}
	printf("%d", mx);
	return 0;
}