[17142번] 연구소 3

문제 출처 :

 

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

 

 

 

 

알고리즘 분석 :

문제 해결에 필요한 사항

1. 순열

2. bfs

3. 문제 이해

 

이 문제는 주어진 비활성 바이러스(2) 중 m개를 뽑아 활성 바이러스(3)으로 바꿔주고, 그 후 bfs를 통해 활성 바이러스는 상/하/좌/우 로 움직이도록 만들어주면 된다.

 

이때 도로(0)을 지나갈 때는 활성 바이러스가 되고 비활성바이러스는 활성바이러스를 만나면 활성바이러스가 됨을 이용하면 된다. 

 

 

 

 

 

소스 코드 : 

 

 

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

#define ROAD 0
#define NON_ACTIVE_VIRUS 2
#define ACTIVE_VIRUS 3
#define INF 987654321
using namespace std;
typedef pair<int, int> pii;

int n, m;
int arr[52][52];
bool visit[12];
vector<pii> virus;

// for bfs
int map[52][52];
int road;

int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,-1,0,1 };

queue<pair<pii, int> > q;

int ans = INF;
int bfs() {
	// clear queue
	while (!q.empty()) { q.pop(); }
	
	// virus qush
	for (int i = 0; i < 12; i++) {
		if (visit[i]) {
			q.push({ virus[i], 0 });

			// this position will be placed initial ACTIVE_VIRUS
			map[virus[i].first][virus[i].second] = ROAD;
			road++;
		}
	}

	int roadCnt = road;
	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int cnt = q.front().second;
		q.pop();

		if (map[y][x] == ROAD) {
			map[y][x] = ACTIVE_VIRUS;
			roadCnt--;
		}
		else if (map[y][x] == NON_ACTIVE_VIRUS)
			map[y][x] = ACTIVE_VIRUS;
		else
			continue;

		if (roadCnt == 0)
			return cnt;

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (0 <= ny && ny < n && 0 <= nx && nx < n) {
				if (map[ny][nx] == ROAD) 
					q.push({ {ny,nx}, cnt + 1 });
				else if (map[ny][nx] == NON_ACTIVE_VIRUS) 
					q.push({ {ny,nx}, cnt + 1 });
			}
		}
	}

	return INF;
}

// copy map for check count of road and use in bfs
void copyMap(int map[][52]) {
	road = 0;

	// copy map
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			map[i][j] = arr[i][j];
			if (map[i][j] == ROAD) {
				road++;
			}
		}
	}
}

// basic combination
void combination(int pos, int cnt) {
	if (cnt == m) {
		copyMap(map);

		int ret = bfs();
		ans = min(ans, ret);
		return;
	}
	for (int i = pos; i < virus.size(); i++) {
		visit[i] = true;
		combination(i + 1, cnt + 1);
		visit[i] = false;
	}
}
int main() {
	scanf("%d %d", &n, &m);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &arr[i][j]);
			if (arr[i][j] == NON_ACTIVE_VIRUS) {
				virus.push_back({ i,j });
			}
		}
	}
	combination(0, 0);

	printf("%d", ans == INF ? -1 : ans);

	return 0;
}

//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>