백준17141 - 연구소 2

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

17141번: 연구소 2

조합과 bfs를 이용하여 해결한 문제이다.

 

우선 좌표정보를 입력받을 때 0과 1과 2를 조건문을 이용하여 입력받았다.

0일 경우 : 빈 공간으로 삽입하려는 좌표 공간에 0을 그대로 입력하고 빈 공간의 갯수를 증가시킨다.

1일 경우 : 벽이므로 삽입하려는 좌표 공간에 -1로 입력한다.

2일 경우 : 바이러스가 존재 가능한 공간 이므로 벡터를 만들어 현재 위치를 저장한다. 삽입하려는 좌표 공간에 0을 입력한 뒤 빈 공간의 갯수를 증가시킨다.

 

바이러스가 존재 가능한 공간을 combination을 이용하여 M개 만큼 검출한다. combination은 dfs를 이용하여 구현한다.

중복을 허락하지 않기 때문에 방문 여부 변수를 만든다.

 

M개 만큼 바이러스 공간을 뽑았다면 bfs를 이용하여 탐색을 한다. 각각의 케이스마다 bfs를 수행할 좌표 공간을 따로 만들어 제일 처음에 입력 받았던 좌표 공간으로 초기화시킨다. 그리고 빈 공간의 갯수도 임시 변수를 만들어 삽입한다. 그 다음 큐에 M개 뽑은 바이러스를 삽입한다. 큐에 삽입할 때 각각의 바이러스는 방문처리한다. 그 다음 bfs를 수행하여 상하좌우로 좌표를 이동하여 유효한 좌표 범위이고 빈 공간이고 방문하지 않은 공간이면 바이러스를 퍼뜨리고 방문 처리한다. bfs를 수행한 결과 빈 공간이 남아있지 않다면 가장 멀리 간 시간을 반환하고 그렇지 않다면 -1을 반환한다.

 

최종적으로 모든 빈 공간을 사라지게 한 가장 짧게 걸린 시간을 출력한다. 빈 공간이 하나라도 존재하면 -1을 출력한다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
#define MAX 51
using namespace std;

int N, M; //N은 좌표 크기, M은 바이러스 갯수
int mat[MAX][MAX]; //입력할 좌표 정보
int cnt = 0; //빈 칸의 갯수
int num; //각 좌표 정보를 입력할 변수
bool visit[MAX][MAX]; //좌표 방문 여부
int small = 987654321; //가장 짧게 걸리는 시간
vector<pair<int, int>> virus; //바이러스가 존재할 수 있는 위치
vector<pair<int, int>> pick; //바이러스 고른 결과
vector<bool> check; //바이러스 위치 고른 여부

//상하좌우
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };

//(x, y)까지 k시간이 걸렸다.
class Point {
public:
	int x, y, k;
	Point(int x, int y, int k) {
		this->x = x;
		this->y = y;
		this->k = k;
	}
};

int bfs() {
	queue<Point> q; //바이러스가 있는 장소를 큐로 넣는다.
	int d[MAX][MAX]; //bfs로 탐색할 공간
	int big = -1; //각 케이스마다 가장 멀리간 바이러스의 시간
	int temp = cnt; //각 케이스 마다 존재하는 빈칸의 갯수

	//각각의 케이스마다 탐색할 공간을 입력 받은 공간으로 초기화 
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			d[i][j] = mat[i][j];
		}
	}

	//초기 바이러스 위치 삽입
	for (int i = 0; i < pick.size(); i++) {
		q.push(Point(pick[i].first, pick[i].second, 0));
		visit[pick[i].first][pick[i].second] = true;
	}

	while (!q.empty()) {
		//맨 앞에 원소 추출하고 삭제
		int x = q.front().x;
		int y = q.front().y;
		int k = q.front().k;
		q.pop();

		temp--; //빈 공간 하나씩 줄이기

		big = max(big, k);

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

			if (1 <= nx && nx <= N && 1 <= ny && ny <= N && !visit[nx][ny] && d[nx][ny] == 0) { //유효 범위이고 방문 안한 공간이고 빈 공간이면
				d[nx][ny] = k + 1;
				q.push(Point(nx, ny, k + 1));
				visit[nx][ny] = true;
			}
		}
	}

	if (temp == 0) { //빈 공간이 없으면
		return big; //가장 멀리 간 시간을 반환
	}
	else { //빈 공간이 있으면
		return -1; //다 퍼뜨리지 못했으니까 -1 반환
	}
}

//combination 구현, 중복 허락X
void dfs(int x, int y) {
	if (y == M) { //M개 뽑았으면
		memset(visit, false, sizeof(visit));
		int ok = bfs(); //바이러스 퍼뜨리는데 가장 오래 걸린 시간을 반환
		if (ok != -1) { //다 퍼뜨렸으면
			small = min(small, ok); //바이러스 퍼뜨리는데 가장 적게 걸린 시간을 찾음
		}
		return;
	}
	for (int i = x; i < virus.size(); i++) { //바이러스를 조합 가능한 경우 모두 탐색
		if (check[i]) { //방문한 바이러스면
			continue; //무시
		}
		pick.push_back(virus[i]); //바이러스 선택
		check[i] = true; //방문처리
		dfs(i + 1, y + 1); //다음 인덱스부터 다시 탐색
		pick.pop_back(); //제일 마지막에 선택한 원소 삭제
		check[i] = false; //제일 마지막에 방문한 원소 미방문 처리
	}
}

int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> num;
			if (num == 0) { //빈 칸으로 입력 받은 경우
				mat[i][j] = 0; //0으로 초기화
				cnt++; //빈 공간의 갯수를 증가
			}
			else if (num == 1) { //벽인 경우 1로 입력하면 bfs 도중에 얼마 걸려서 바이러스를 옮겼는지 헷깔리니까 
				mat[i][j] = -1; //-1로 넣는다.
			}
			else { //바이러스가 있을 수 있는 칸으로 입력 받은 경우
				mat[i][j] = 0; //바이러스가 존재한다고 확신을 못하니까 우선 빈 칸으로 초기화
				virus.push_back(pair<int, int>(i, j)); //바이러스가 존재할 수 있는 칸이니까 벡터에 삽입
				check.push_back(false); //현재 삽입한 바이러스 존재 가능 칸을 미방문처리하여 벡터에 삽입
				cnt++; //빈 공간의 갯수 증가
			}
		}
	}

	dfs(0, 0); //바이러스를 M개 만큼 조합 시작


	if (small == 987654321) { //바이러스가 모두 사라지지 않았다면
		cout << -1; //-1출력
	}
	else { //바이러스가 모두 사라지면
		cout << small; //최소 시간 출력
	}
}