[Algorithm][C++] BOJ 17142 연구소 3

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

17142번: 연구소 3

 

풀이 핵심

1. Bruth Force + BFS 문제

 

2. blank 변수에 빈칸 (0)의 개수를 저장 한다.

 

3. virus를 활성화 시킬 수 있는 장소(2)의 위치 (r, c) 를 virus 배열에 저장한다. (virus_size 변수에 virus 배열 장소 개수도 같이 저장)

 

4. 활성화 위치를 저장할 vector picked를 생성하고 재귀 형식의 dfs 함수에 전달한다. dfs 함수는 vector picked와 index를 입력 인자로 받는다.

 

5. 활성화 위치를 저장한 picked.size()가 M과 같으면 bfs에 picked vector를 전달하고 bfs를 실행한다.

 

6. cur_blank 변수에 빈칸 개수를 저장하고 만약 cur_blank가 0이면 0을 return 한다. 그렇지 않으면 check 배열을 생성한다. check 배열은 중복 방문 방지 및 시간 저장용이다.

 

7. cur_blank가 0이 되면 시간 (check[nr][nc]) 을 return 한다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <queue>
#include <vector>
#include <string.h>
using namespace std;

struct POS { int r, c; };
int n, m;
int map[50][50];
int blank; // 빈 칸 개수
POS virus[250]; // virus 활성화 가능 위치 저장
int virus_size; // virus 활성화 가능 위치 개수
int ans = -1;
const int dr[] = { 0,0,1,-1 };
const int dc[] = { 1,-1,0,0 };

int bfs(vector<POS> picked) {
	int cur_blank = blank; // 빈 칸 개수 저장
	if (cur_blank == 0) return 0; // 시작 빈 칸 개수가 0이면 0 return

	int check[50][50]; // 중복 방문 및 시간 저장
	memset(check, -1, sizeof(check)); // -1로 초기화

	queue<POS> q;
	for (int i = 0; i < picked.size(); i++) {
		q.push(picked[i]);
		check[picked[i].r][picked[i].c] = 0;
	}

	while (!q.empty()) {
		POS cur = q.front();
		q.pop();
		for (int dir = 0; dir < 4; dir++) {
			int nr = cur.r + dr[dir];
			int nc = cur.c + dc[dir];
			if (nr < 0 || nr >= n || nc < 0 || nc >= n)continue;
			if (check[nr][nc] != -1 || map[nr][nc] == 1) continue;
			q.push({ nr,nc });
			check[nr][nc] = check[cur.r][cur.c] + 1;
			if (map[nr][nc] == 0) // 방문한 위치가 빈 칸이면 cur_blank 감소
				--cur_blank;
			if (cur_blank == 0) return check[nr][nc]; // 시간 return
		}
	}
	// 빈 칸에 모두 방문 하지 못했으므로 -1 return
	return -1;
}

void dfs(vector<POS> picked, int idx) {
	if (picked.size() == m) {
		int ret = bfs(picked);
		if (ret != -1) {
			if (ans == -1 || ans > ret) {
				ans = ret;
			}
		}
	}
	for (int i = idx + 1; i < virus_size; i++) {
		picked.push_back(virus[i]);
		dfs(picked, i);
		picked.pop_back();
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for (int r = 0; r < n; r++) {
		for (int c = 0; c < n; c++) {
			scanf("%d", &map[r][c]);
			if (map[r][c] == 0) {
				blank++;
			}
			else if (map[r][c] == 2) {
				virus[virus_size++] = { r,c };
			}
		}
	}
	vector<POS> picked;
	dfs(picked, -1);
	printf("%d", ans);
	return 0;
}