17142 Samsung sw test

์ฝ”๋“œ

#include <iostream>
#include <cstring>
#include <vector>
#include <list>
#include <algorithm>
#define MAX_WIDTH 50
#define WALL 1
 
using namespace std;
int map[MAX_WIDTH][MAX_WIDTH];
 
typedef struct Virus {
	int row;
	int col;
	int time;
 
	bool operator < (Virus v) {
		if (map[row][col] == 2 && map[v.row][v.col] != 2)
			return false;
		else if (map[row][col] != 2 && map[v.row][v.col] == 2)
			return true;
		else
			return time > v.time;
	}
} Virus;
 
int width, numOfActiveVirus, numOfVirus;
vector<Virus> virus;
bool canSpread = false;
 
int minToSpreadVirus(vector<Virus> active, int deep);
int min(int a, int b);
 
int main() {
	cin >> width >> numOfActiveVirus;
	numOfVirus = 0;
	for (int i = 0; i < width; i++) {
		for (int j = 0; j < width; j++) {
			cin >> map[i][j];
			if (map[i][j] == 2) {
				virus.push_back({ i, j, 0});
				numOfVirus++;
			}
		}
	}
	vector<Virus> temp;
	int result = minToSpreadVirus(temp, 0);
	if (result == -1 && canSpread)
		cout << 0;
	else
		cout << minToSpreadVirus(temp, 0);
}
 
int minToSpreadVirus(vector<Virus> active, int deep) {
	if (active.size() == numOfActiveVirus) {
		//ํผํŠธ๋ฆฌ๊ธฐ
		list<Virus> q;
		bool visit[MAX_WIDTH][MAX_WIDTH] = { 0, };
		for (int i = 0; i < active.size(); i++) {
			q.push_back(active[i]);
			visit[active[i].row][active[i].col] = true;
		}
 
		vector<Virus> minTimeCandidate;
		while (!q.empty()) {
			Virus v = q.front();
			q.pop_front();
 
			int count = 0;
			if (v.row > 0 && !visit[v.row - 1][v.col] && map[v.row - 1][v.col] != 1) {
				q.push_back({ v.row - 1, v.col, v.time + 1 });
				visit[v.row - 1][v.col] = true;
				if(map[v.row-1][v.col] == 0)
					count++;
			}
			if (v.col < width - 1 && !visit[v.row][v.col + 1] && map[v.row][v.col + 1] != 1) {
				q.push_back({ v.row, v.col + 1, v.time + 1 });
				visit[v.row][v.col + 1] = true;
				if(map[v.row][v.col+1] == 0)
					count++;
			}
			if (v.row < width - 1 && !visit[v.row + 1][v.col] && map[v.row + 1][v.col] != 1) {
				q.push_back({ v.row + 1, v.col, v.time + 1 });
				visit[v.row + 1][v.col] = true;
				if(map[v.row+1][v.col]==0)
					count++;
			}
			if (v.col > 0 && !visit[v.row][v.col - 1] && map[v.row][v.col - 1] != 1) {
				q.push_back({ v.row, v.col - 1, v.time + 1 });
				visit[v.row][v.col - 1] = true;
				if(map[v.row][v.col-1] == 0)
					count++;
			}
 
			if (count == 0)
				minTimeCandidate.push_back(v);
		}
 
		for (int i = 0; i < width; i++)
			for (int j = 0; j < width; j++)
				if (!visit[i][j] && map[i][j] != 1)
					return -1;
 
		canSpread = true;
		sort(minTimeCandidate.begin(), minTimeCandidate.end());
		if (map[minTimeCandidate[0].row][minTimeCandidate[0].col] == 2)
			return -1;
		else
			return minTimeCandidate[0].time;
 
	}
	if (numOfVirus - deep < numOfActiveVirus - active.size())
		return -1;
 
	int a = minToSpreadVirus(active, deep + 1);
	active.push_back(virus[deep]);
	int b = minToSpreadVirus(active, deep + 1);
 
	return min(a, b);
}
int min(int a, int b) {
	if (a == -1)
		return b;
	else if (b == -1)
		return a;
	else
		return a < b ? a : b;
}