[백준 14502] 연구소

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

14502번: 연구소

 

요구사항

1. 벽 3개 짓기

2. bfs로 바이러스 퍼트리기

 

풀이

1. dfs로 벽3개 위치를 선정한다

2. bfs로 바이러스를 퍼트린다.

3. 안전 구역 영역의 개수를 카운트하고 ans랑 비교한다.

 

tip

벽을 지을때 중복안되게 하니깐 시간이 372-> 60으로 줄었다

 

#include <iostream>
#include <queue>
#include <string.h>
#include <algorithm>
using namespace std;

int map[9][9];
int n, m;
struct go {
	int x;
	int y;
};
int visit[9][9];
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,1,0,-1 };
int ans = 0;
void dfs(int r, int c, int cnt) {
	if (cnt == 3) {
		queue<go> q;
		int visit[9][9] = { 0, };
		int mapc[9][9];
		memcpy(mapc, map, sizeof(map));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (mapc[i][j] == 2 && visit[i][j] == 0) {
					queue<go> q;
					q.push({ i,j });
					visit[i][j] = 1;
					while (!q.empty()) {
						int r = q.front().x;
						int c = q.front().y;
						q.pop();
						for (int i = 0; i < 4; i++)
						{
							int nr = r + dr[i];
							int nc = c + dc[i];
							
							if (nr < 0 || nc < 0 || nr >= n || nc >= m)
								continue;
							
							if (mapc[nr][nc] == 0 && visit[nr][nc] == 0) {
								mapc[nr][nc] = 2;
								visit[nr][nc] = 1;
								q.push({ nr,nc });
							}
						}
					}
				}
			}
		}
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (mapc[i][j] == 0)
				{
					cnt++;
				}
			}
		}
		if (ans < cnt) {
			ans = cnt;
		}
		return;
	}

	for (int i = r; i < n; i++)
	{
		for (int j = c; j < m; j++) {
			if (map[i][j] == 0) {
				map[i][j] = 1;
				dfs(i,j,cnt + 1);
				map[i][j] = 0;
			}
		}
		c = 0;
	}
}
int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &map[i][j]);
		}
	}

	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,1);
				map[i][j] = 0;
			}
		}
	}

	cout << ans << endl;

}