[백준] 14502번 연구소

백준 14502번 연구소 C++ 풀이

 

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

 

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int map[8][8];
int temp[8][8];

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

int N, M;
int ans = 0;

void copyMap(int a[8][8], int b[8][8]) {

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			a[i][j] = b[i][j];
		}
	}

}

void bfs() {

	int spread[8][8];

	copyMap(spread, temp);

	queue <pair<int, int>> q;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (temp[i][j] == 2)
				q.push({ i,j });
		}
	}

	while (!q.empty()) {

		int x = q.front().first;
		int y = q.front().second;
		q.pop();

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

			if (nx < 0 || ny < 0 || nx >= N || ny >= M)
				continue;
			else {
				if (spread[nx][ny] == 0) {
					spread[nx][ny] = 2;
					q.push({ nx,ny });
				}
			}
		}
	}

	int cnt = 0;

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

	ans = max(ans, cnt);

}

void recursive(int cnt) {

	if (cnt == 3) {
		bfs();
		return;
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (temp[i][j] == 0) {
				temp[i][j] = 1;
				recursive(cnt + 1);
				temp[i][j] = 0;
			}
		}
	}

}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;

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

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 0) {
				copyMap(temp, map);
				temp[i][j] = 1;
				recursive(1);
				temp[i][j] = 0;
			}

		}
	}

	cout << ans << "\n";

}