[알고리즘] c++ cpp 연구소시리즈 (연구소2)

포인트

1. bfs 를 잘 할 수 있는가?

2. 최소 시간을 알 수 있는가?

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

#include <iostream>
#include <queue>
#include <vector>
#include<cstring>
#include <algorithm>
#include <tuple>

using namespace std;
#define MAX 50
#define VIRUS_MAX 10

int map[MAX][MAX];
int dist[MAX][MAX];
int n, m;
int cnt = 0;
int answer = 987654321;
vector<pair<int, int>> virus;
vector<pair<int, int>> real_virus;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void bfs() {
	queue<pair<int, int>> q;

	for(auto ele : real_virus) {
		q.push ({ ele.first, ele.second });
		dist[ele.first][ele.second]=0;
	}

	int check = 0;
	int time = 0;
	while (!q.empty()) {
		int x, y;
		tie(x, y) = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; // 범위 체크
			if (map[nx][ny] == 1 || dist[nx][ny] != -1) continue; // 조건 넣기
			q.push(make_pair(nx, ny));
			dist[nx][ny] = dist[x][y] + 1;

			if (map[nx][ny] == 0) {
				check++;
				time = dist[nx][ny];
			}
		}
	}

	if (check == cnt)
		answer = min(answer, time);
}

void go(int index, int cnt) {
	if (cnt == m) {
		memset(dist, -1, sizeof (dist));
		bfs();
		return;
	}

	if (index >= virus.size()) return;

	real_virus.push_back(virus[index]);
	go(index + 1, cnt + 1);
	real_virus.pop_back();


	go(index + 1, cnt);
}

int main() {
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (map[i][j] == 2) // 바이러스
				virus.push_back({i, j});

			if (map[i][j] == 0) //숫자를 센다.
				cnt += 1;
		}
	}

	go(0, 0);
	if (answer == 987654321) cout << -1 << '\n';
	else cout << answer << '\n';

}