백준 17142 연구소3(bfs dfs)

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

17142번: 연구소 3

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
int map[51][51];
int visited[51][51];
int temp[51][51];
int result;
vector<pair <int, int>> v;
queue <pair< pair<int, int>,int>> q;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

void init() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			map[i][j] = temp[i][j];
			visited[i][j] = 0;
		}
	}
}

int minVal() { // 최솟값 구하기
	int minVal=0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 0) {
				return -1;
			}
			else if(map[i][j] && visited[i][j] !=0) {
				minVal = max(minVal, map[i][j]);
			}
		}
	}
	return minVal;
}


void bfs(int val) { //바이어스 퍼지기

	for (int i = 0; i < m; i++) {
		int num = val % 10;
		val /= 10;
		q.push({ { v[num].first,v[num].second },1 });
	}	
	while (!q.empty()) {

		int x = q.front().first.first;
		int y = q.front().first.second;
		int cnt = q.front().second;
		map[x][y] = cnt;
		//map[x][y] = cnt;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int cx = x + dx[i];
			int cy = y + dy[i];
			if (cx >= 0 && cx < n && cy >= 0 && cy < n) {
				if (visited[cx][cy] == 0 && (map[cx][cy] == 0 || map[cx][cy] == 2)) {
					if (map[cx][cy] != 2) visited[cx][cy] = 1;
					q.push({{cx,cy},cnt + 1 });
				}
			}
		}
		
	}

}


void dfs(int t,int start,int val) { // 바이러스 개수중 m개만 선택
	if (t == 1) {
		init();
		bfs(val);
		int minV = minVal();
		if (minV != -1) {
			if (result == -1) result = 987654321;
			result = min(minV, result);
		}
		return;
	}
	int size = v.size();
	for (int i = start + 1; i < size; i++) {
		dfs(t - 1, i, val * 10 + i);
	}

}


int main(){
	result = -1;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &temp[i][j]);
			map[i][j] = temp[i][j];
			visited[i][j] = 0;
			if (map[i][j] == 2) {
				v.push_back({ i,j });
			}
		}
	}
	
	if (minVal() == 0) {
		printf("0");
		return 0;
	}

	for(int i = 0; i < v.size(); i++) {
		dfs(m, i, i);
	}
	
	if (result == -1||result == 987654321) {
		result = 0;
	}
	printf("%d", result-1);
	return 0; 

}