[백준OJ] 14502번 연구소

www.acmicpc.net/problem/14502

14502번: 연구소

---

 

-풀이-

1. 입력을 받으며 0의 위치들을 기록해준다.

2. 입력받은 0의 위치들에 대해 백트래킹을 실행해준다. 

3. 0의 위치중 순서 상관없이 3개를 골라, 1로 만들어준뒤, bfs를 실행하여 바이러스를 확산시킨다.

4. 바이러스를 확산시킨뒤, 배열을 탐색하며 바이러스가 퍼지지않은 구역을 카운팅해주고, 최댓값을 업데이트 해준다.

 

-시간 복잡도-

일단 백트래킹의 경우, 조합을 이용한 것이므로, 바이러스가 2개있고, 나머지는 다 열린공간이 최악의 경우이다.

이때 걸리는 시간은 (64-2)C3 이 걸린다. 이것은 O((N*M)^3) 이 된다.

각 조합당 bfs를 순회하는 시간은 M*N의 시간이 걸리므로 O(M*N)이 된다.

따라서 총 O((N*M)^4) 이 되지만, N과M의 최댓값이 8씩이므로, 작은 수여서 시간안에 들어온다.

 

-코드-

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

int maze[8][8];
int mv[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
int n, m;
vector<pair<int, int>> zero,virus;
int max_size = -1;

bool isIn(int x, int y) {
	return x >= 0 && x < n&&y >= 0 && y < m;
}

void bfs() {
	queue<pair<int, int>> q;
	int copy_maze[8][8];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			copy_maze[i][j] = maze[i][j];
		}
	}

	for (int i = 0; i < virus.size(); i++) {
		q.push({ virus[i].first,virus[i].second });
	}

	while (!q.empty()) {
		int nowx = q.front().first;
		int nowy = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = nowx + mv[i][0];
			int ny = nowy + mv[i][1];

			if (isIn(nx, ny) && copy_maze[nx][ny] == 0) {
				copy_maze[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 (copy_maze[i][j] == 0) cnt++;
		}
	}
	max_size = max(max_size, cnt);
	return;
}

void backtracking(int ind, int count) {
	if (count == 3) {
		bfs();
		return;
	}
	for (int i = ind + 1; i < zero.size(); i++) {
		int x, y;
		x = zero[i].first;
		y = zero[i].second;
		maze[x][y] = 1;
		backtracking(i, count + 1);
		maze[x][y] = 0;
	}
	return;
}

int main(){
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> maze[i][j];
			if (maze[i][j] == 0) {
				zero.push_back({ i,j });
			}
			else if (maze[i][j] == 2) {
				virus.push_back({ i,j });
			}
		}
	}
	for (int i = 0; i < zero.size() - 2; i++) {
		int x, y;
		x = zero[i].first;
		y = zero[i].second;
		maze[x][y] = 1;
		backtracking(i, 1);
		maze[x][y] = 0;
	}
	cout << max_size << "\n";
}