[성실코딩 8일차] 백준 #14502 연구소 / DFS, BFS *

풀긴 풀었는데 기분 나빠아아아아ㅏ 너무 더럽게 푼 느낌이야 ㅠㅠ 더 깔끔하게 할 수 잇을 것 같은데!!!!!!!!!!!!!!

글고 이거 문제에서 제한하는 시간이 2초가 아니라 1초였으면 백퍼 시간초과 나왔겠지

근데 낼 중간고사 시험이라 마음이 급한 것 같다 ㅠㅠ 

시험 끝나고 다시 공부해봐야지

#include<iostream>
#include<cstring> // memcpy -> 백준에서 쓰기위해

using namespace std;

int n, m;
int table[9][9] = {0,};
int copied_table[9][9] = { 0, };
int barrier_visited[9][9] = { 0, };


int barrier_cnt = 0;
int biggist_area = 0;

// 상하좌우
int di[4] = {-1,1,0,0};
int dj[4] = {0,0,-1,1};

void virus(int _x, int _y) {
	for (int k = 0; k < 4; k++) {
		int x = _x + di[k];
		int y = _y + dj[k];
		if ((x < 0 || x >= n) ||
			(y < 0 || y >= m) ) { // 범위에 벗어나거나 
			continue;
		}
		else if (copied_table[x][y] != 0) { //벽있는경우 pass
			continue;
		}
		else { // table[x][y]=0
			   // 퍼져나갈수 있음
			copied_table[x][y] = 2;
			virus(x,y);
		}
	}
	return;
}

void findFirst2() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (table[i][j] == 2) {
				virus(i, j);
			}
		}
	}
	return;
}

void check() {
    int temp_cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (copied_table[i][j] == 0) {
				temp_cnt++;
			}
		}
	}
	if (temp_cnt > biggist_area) {
		biggist_area = temp_cnt;
	}
}

void dfs() {

	if (barrier_cnt==3) { // 벽 3개 다 세웠음

		// 2가 갈 수 있는 곳들 다 표시
		findFirst2();

		// 안전영역 갯수 세기
		check(); 

		return;
	}
	else { // 3이 아닐 경우, 방어벽 세워주기.
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (barrier_visited[i][j] == 0) {
					// 방문한 적도 없고, 벽도 현재 없음 -> 세울 수 잇음
					barrier_visited[i][j] = 1;
					table[i][j] = 1;
					copied_table[i][j] = 1;
					barrier_cnt++;
					dfs();
					
					// 초기화
					table[i][j] = 0;
					barrier_visited[i][j] = 0;
					memcpy(copied_table, table, sizeof(int)*9*9);
					barrier_cnt--;
				}
			}
		}
	}
}

int main() {

	// 입력 받기
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> table[i][j];
			
			// 초기화
			copied_table[i][j] = table[i][j];
			barrier_visited[i][j] = table[i][j];
		}
	}
	
	// 연산
	dfs();

	// 출력
	cout << biggist_area << endl;

	return 0;
}