[C/C++] 백준 - 17141번 (연구소2)

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

17141번: 연구소 2

이 문제는 지금껏 접해본 문제들과 많이 비슷하지만

꼭 기억하고 넘어가야 할 방법이 존재해 기록해두려한다.

 

좌표값들 중 조합을 이용할 경우

-> 벡터와 배열을 이용할 수 있다.

// 좌표값 중 특정한 값에 대해 추출해야할 경우
// 예를 들어, 5X5 크기의 MAP이 존재하고 그 중 2를 value로 가지는 값 2개를 뽑아야할 경우
void Init(){
	for(int i=0;i<5;i++){
    	for(int j=0;j<5;j++){
        	cin >> map[i][j];
            if(map[i][j] == 2){
            	v.push_back({i,j});
            }
        }
	}
}

// 이것을 조합을 이용해 선택하는 경우
void Select(int depth, int cnt) {
	if (cnt == M) {
		memset(visited, false, sizeof(visited));
		bfs_spread();
		return;
	}

	for (int i = depth; i < v.size(); i++) {
		if (select_virus[i] == true)
			continue;
		select_virus[i] = true;
		virus.push_back(v[i]);
		Select(i, cnt + 1);
		select_virus[i] = false;
		virus.pop_back();
	}
}

좌표값들 중 조합을 이용해 뽑아내는 경우가 어려웠는데 벡터와 배열을 사용하면 해결할 수 있다.

 

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<queue>
#include<deque>
#define MAX_SIZE 50+3
#define INF 987654321

using namespace std;

int N, M; 
int times;
int result = INF;
int map[MAX_SIZE][MAX_SIZE];
int copy_map[MAX_SIZE][MAX_SIZE];

bool visited[MAX_SIZE][MAX_SIZE];
bool select_virus[MAX_SIZE];

// 0은 빈칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
queue<pair<int, int>> q;
vector<pair<int, int>> v;
vector<pair<int, int>> virus;

bool Check_not_visit() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 1) continue;
			if (visited[i][j] == false) return false;
		}
	}
	return true;
}

void bfs_spread() {
	int nextX, nextY;
	for (int i = 0; i < virus.size(); i++) {
		int x = virus[i].first;
		int y = virus[i].second;
		q.push({ x,y });
		visited[x][y] = true;
	}

	times = 0;
	while (!q.empty()) {
		int qs_s = q.size();
		for (int qs = 0; qs < qs_s; qs++) {
			int cur_x = q.front().first;
			int cur_y = q.front().second;
			q.pop();

			for (int i = 0; i < 4; i++) {
				nextX = dx[i] + cur_x;
				nextY = dy[i] + cur_y;

				if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N) continue;
				if (visited[nextX][nextY] == false && map[nextX][nextY] != 1) {
					visited[nextX][nextY] = true;
					q.push({ nextX,nextY });
				}
			}
		}
		if (q.size() != 0) times++;
	}
	if (Check_not_visit())
		result = min(result, times);
}
void Print() {
	cout << "\n";
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout <<copy_map[i][j] << "  ";
		}
		cout << "\n";
	}
	cout << "\n";
}

void Select(int depth, int cnt) {
	if (cnt == M) {
		memset(visited, false, sizeof(visited));
		bfs_spread();
		return;
	}

	for (int i = depth; i < v.size(); i++) {
		if (select_virus[i] == true)
			continue;
		select_virus[i] = true;
		virus.push_back(v[i]);
		Select(i, cnt + 1);
		select_virus[i] = false;
		virus.pop_back();
	}
}

void Input() {
	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) v.push_back({ i,j });
		}
	}
}

int main(void) {
	Input();
	Select(0,0);
	if (result == INF) result = -1;
	cout << result << endl;

	return 0;
}