백준 17142 c++ "연구소 3" -[PlusUltraCode]

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

17142번: 연구소 3

 

[필자 사고]

 

BFS 구현문제이다.

 

문제에서 조심해야 되는 부분이 많은 문제다.

 

4 1
1 1 1 1
0 2 2 0
1 1 1 1
1 1 1 1    이러한 경우는 답이 2초다. 1초가 아니다.

이 부분에서 답이 틀린 이유는  이미 존재하는 비활성화 상태인 바이러스와 만날경우에 대한 로직을 잘못 짯을 것이다.

이 문제에서 요구하는 비활성화 상태인 바이러스와 만나면 그냥 원래 시간에서 +1해주면 된다. 깊게 고민하지 않아도 된다.

3 1
2 1 1
1 1 2
1 1 1  다음으로 조심해야 되는 경우다ㅏ. 답은 0이다. -1로 실수할 수있는 경우이다.

 

활성바이러스를 선택 하든 안하든 이미 모든 인덱스 에서 바이러스가 있기 때문에 0초의 답을 도출할 수 있다.

 

이정도가 조심해야 될 점이다.

 

이제 문제 풀이를 시작하겠다.

 

조합을 이용하여 여러개의 바이러스중 M개를 선택하기 위해 재귀를 이용하였다. 전형적인 조합 알고리즘을 이용하면 쉽게 접근할 수 있다.

 

다음으로 바이러스가 퍼지는 시간을 구하기 위해 BFS 너비우선탐색을 이용하여 문제를 해결할 수 있다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
using namespace std;
int N, M;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
typedef pair<int, int> Node;
vector<vector<int>> Arr;
vector<Node> birusTank;
stack<Node> myStack;
vector<int> Result;
bool birusVisited[51][51];

bool Inside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < N)return true;
	return false;
}

void Input() {
	cin >> N >> M;
	Arr.resize(N);
	for (int i = 0; i < N; i++) {
		Arr[i].resize(N);
		
	}
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			int num;
			cin >> num;
			Arr[i][k] = num;
			if (num == 2) {
				birusTank.push_back({ i,k });
			}
		}
	}

}
vector<vector<bool>> visited;
vector<vector<int>> pathLoad;
void gameStart() {
	visited.clear();
	pathLoad.clear();
	visited.resize(N);
	pathLoad.resize(N);
	for (int i = 0; i < N; i++) {
		visited[i].resize(N, false);
		pathLoad[i].resize(N, -1);
	}
	queue<Node> myQueue;
	stack<Node> myStack2 = myStack;
	while (!myStack2.empty()) {
		int sero = myStack2.top().first;
		int garo = myStack2.top().second;
		myStack2.pop();
		myQueue.push({ sero,garo });
		visited[sero][garo] = true;
		pathLoad[sero][garo] = 0;
	}

	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) == false)continue;
			if (visited[nextSero][nextGaro] == true)continue;
			//방문안한 상태에서 
			//1이 아니어야하고
			//2인경우
				//그냥 시간초 전이 
			//0인 경우
				//+1 시간초 전이

			if (Arr[nextSero][nextGaro] == 1)continue;
			if (Arr[nextSero][nextGaro] == 2) {
				pathLoad[nextSero][nextGaro] = pathLoad[nowSero][nowGaro]+1;
				myQueue.push({ nextSero,nextGaro });
				visited[nextSero][nextGaro] = true;
			}
			else if (Arr[nextSero][nextGaro] == 0) {
				pathLoad[nextSero][nextGaro] = pathLoad[nowSero][nowGaro] + 1;
				myQueue.push({ nextSero,nextGaro });
				visited[nextSero][nextGaro] = true;
			}
		}
	}
	int maxNum = 0;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			if (Arr[i][k] == 1)continue;
			if (Arr[i][k] == 2)continue;
			if (pathLoad[i][k] == -1) {
				maxNum = -1;
				Result.push_back(maxNum);
				return;
			}
			if (pathLoad[i][k] >= maxNum) {
				maxNum = pathLoad[i][k];
			}
		}
	}
	Result.push_back(maxNum);
	return;
	

	//이거 진행가되면 
	//모든곳이다 퍼져있는지 확인해야돼
	//그 모든원소의 최댓갑솨 결과값을 비교하여 작은값 택
}

void Combination_Start(int start,int count) {
	if (count == M) {
		gameStart();
		return;
	}
	for (int i = start; i < birusTank.size(); i++) {
		int sero = birusTank[i].first;
		int garo = birusTank[i].second;
		myStack.push({ sero,garo });
		Combination_Start(i + 1, count + 1);
		myStack.pop();
		
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
	Combination_Start(0, 0);
	int minNumber = 100000;
	for (int i = 0; i < Result.size(); i++) {
		if (Result[i] == -1)continue;
		if (Result[i] < minNumber) {
			minNumber = Result[i];
		}
	}
	if (minNumber == 100000)cout << -1;
	else cout << minNumber;
}