백준 14502 연구소.

#include 
#include 
#include 
using namespace std;

typedef struct {
	int position_x;
	int position_y;
}desease;

int Map[8][8];
int copy_map[8][8];
int x, y;
int Max_count = 0;
int i_count;
int j_count;
int k_count;
int q_count;
int result = 0;
int dirx[4] = { -1,1,0,0 };
int diry[4] = { 0,0,-1,1 };
queue initial_q;

void Input() {
	scanf("%d %d", &y, &x);
	for (int i = 0; i < y; i++) {
		for (int j = 0; j < x; j++) {
			scanf("%d", &Map[i][j]);
			if (Map[i][j] == 2) initial_q.push({ j,i });
		}
	}
}

void Copy_one_Map(){
	for (int l = 0; l < y; l++) {
		for (int c = 0; c < x; c++) {
			copy_map[l][c] = Map[l][c];
		}
	}
}

void q_process() {
	queue q(initial_q);
	while (!q.empty()) {
		int q_x = q.front().position_x;
		int q_y = q.front().position_y;
		q.pop();
		for (int h = 0; h < 4; h++) {
			q_count++;
			int next_x = q_x + dirx[h];
			int next_y = q_y + diry[h];
			if (copy_map[next_y][next_x] != 0 || next_x < 0 || next_y < 0 || next_x >= x || next_y >= y) continue;
			copy_map[next_y][next_x] = 2;
			q.push({ next_x, next_y });
		}
	}
}

void calc_result() {
	for (int t = 0; t < y; t++) {
		for (int b = 0; b < x; b++) {
			if (copy_map[t][b] == 0) result++;
		}
	}
}

void print_map() {
	for (int i = 0; i < y; i++) {
		for (int j = 0; j < x; j++) {
			printf("%d ", copy_map[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}

void Copy_Map() {
	for (int i = 0; i < y; i++) {
		for (int j = 0; j < x; j++) {
			copy_map[i][j] = Map[i][j];
		}
	}
}

void Calc() {
	int length = x * y;
	for (int i = 0; i < length; i++) {
		i_count++;
		/*Copy_one_Map();*/
		if (Map[i / x][i%x] != 0) continue;
		Map[i / x][i%x] = 1;
		for (int j = i; j < length; j++) {
			j_count++;
			if (Map[j / x][j%x] != 0) continue;
			Map[j / x][j%x] = 1;
			for (int k = j; k < length; k++) {
				k_count++;
				result = 0;
				if (Map[k / x][k%x] != 0) continue;
				Map[k / x][k%x] = 1;
				Copy_Map();
				/*printf("copy\n");*/
				/*print_map();*/
				q_process();
				calc_result();
				/*printf("i , j , k : %d %d %d \n", i, j, k);*/
				/*print_map();*/
				
				Map[k / x][k%x] = 0;
				if (result > Max_count) Max_count = result;
			}
			Map[j / x][j%x] = 0;
		}
		Map[i / x][i%x] = 0;
	}

	printf("%d", Max_count);
}


int main(void) {
	Input();
	Calc();
	/*Copy_Map();
	q_process();*/
	/*printf("cur_count : %d %d %d %d", i_count, j_count, k_count, q_count);*/


	return 0;
}

어떻게 풀까 생각하다가 든 생각이 미리 벽을 세워놓고 결과를 끝까지 기다렸다가 0인 곳을 세워보자 였다. 하지만 이럴 경우 매트릭스 길이가 늘어나면 시간복잡도가 기하급수적으로 늘어날꺼라 생각하였고 최악의 경우를 생각하며 풀었다. 최악의 경우 1번째는 n(n-1)/2, 2번째는 (n-1)n/2 ..... 64번째 (n-(n-1)(n-(n+1)+1)/2 번 돈다. 지금 분석중인데 등차수열, 등비수열 개념까지 다시 알아야 해서 쉽지가 않다. 조만간 분석해서 올려야겠다............ 아 그리고 최악의 경우 q안에서 n-1번 도는데 그게 4번 반복되니 4(n-1)번 도니 그것까지 곱해줘야 하지만 연산기준 1억을 잡았을때 1초에 이 수치를 넘지 않으니 괜찮다는 생각으로 했다. 백준에 돌려보니 32ms 나왔다. 

반성할점 : 메인안에 모든 로직을 때려박았는데 가면 갈수록 디버깅도 힘들고 가독성도 최악을 달렸다. 따라서 분리할수 있는 부분을 분리하여 그 부분이 잘 작동하나 테스트를 진행하였더니 쉽게 오류를 발견할수 있었다. 분리하고 테스트 기억하자!