14502 백준 c++ -[PlusUltraCode]

[필자 사고]

전형적인 2차원 그래프 탐색문제다

이 문제의 특이한 점은 벽을 세운다라는 점이다.

바이러스가 감염되어 다른 배열에 영향을 끼치는 문제는 수도 없이 풀어 봤을 것이다.

문제의 막히는 주요 원인은 어떻게 벽을 세워 BFS탐색을 수행하는 지다.

 

필자는 다음과 같이 벽을 세우는 방식을 사용했다.

 

1. space 배열에 0이 들어간  index를 모두 넣어주었다.

2. vis라는 배열에는 bool값을 넣어주었다.

 

재귀 함수를 이용하여 space 배열내에 있는 모든 x와 y의 값을 Copy_Arr 에 넣어주어 하나 하나 BFS탐색을 진행시켰다.

 

 

[소스 코드]

 

 

 

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

vector<vector<int>> Arr;
vector<vector<bool>> visited;
vector<pair<int, int>> space;
vector<vector<int>> Copy_Arr;
bool vis[65];

int N, M;
int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };
int MaxResult = -1;
void Input() {
	cin >> N >> M;
	Arr.resize(N);
	visited.resize(N);
	
	for (int i = 0; i < N; i++) {
		Arr[i].resize(M);
		visited[i].resize(M);
	}
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			cin >> Arr[i][k];
			if (Arr[i][k] == 0) {
				space.push_back({ i,k });
			}
		}
	}
	Copy_Arr = Arr;
}
bool Inside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < M)return true;
	return false;
}

void BFS() {
	vector<vector<int>> Copy_Arr2 = Copy_Arr;
	queue<pair<int, int>> myQueue;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			if (Copy_Arr2[i][k] == 2) {
				myQueue.push({ i,k });
				visited[i][k] = true;
			}
		}
	}
	while (!myQueue.empty()) {
		int nowSero = myQueue.front().first;
		int nowGaro = myQueue.front().second;
		myQueue.pop();
		for (int i = 0; i < 4; i++) {
			int nextSero = nowSero + dy[i];
			int nextGaro = nowGaro + dx[i];
			if (Inside(nextSero, nextGaro) &&
				Copy_Arr2[nextSero][nextGaro] == 0 &&
				visited[nextSero][nextGaro] == false) {
				Copy_Arr2[nextSero][nextGaro] = 2;
				visited[nextSero][nextGaro] = true;
				myQueue.push({ nextSero,nextGaro });
			}
			
		}
	}
	
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			if (Copy_Arr2[i][k] == 0) {
				cnt++;
			}
		}
	}
	visited.clear();
	visited.resize(N);
	for (int i = 0; i < N; i++) {
		visited[i].resize(M);
	}
	if (MaxResult < cnt) {
		MaxResult = cnt;
		return;
	}

}

void wall(int cur,int idx) {
	if (cur == 3) {
		Copy_Arr = Arr;
		int cnt = 0;
		for (int i = 0; i < space.size(); i++) {
			if (cnt == 3)break;
			if (vis[i]) {
				cnt++;
				int x = space[i].first;
				int y = space[i].second;
				Copy_Arr[x][y] = 1;

			}
		}
		BFS();
		return;
	}
	for (int i = idx; i < space.size(); i++) {
		if (vis[i])continue;
		vis[i] = true;
		wall(cur + 1, i);
		vis[i] = false;
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
	wall(0,0);
	cout << MaxResult;
}