[백준 17141] 연구소 2

++22.11.10 갱신

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

17141번: 연구소 2

#include <cstdio>
#include <queue>
#include <cstring>
int N, M;	//50 * 50맵, 최대 10개
int board[50 + 2][50 + 2];
int ans = 0x7fffffff;
int wall;
int zeros;

struct _st
{
	int x, y;
};
std::vector<_st> V;
int v_cnt;
int choice[10 + 2];

struct _qt
{
	int x, y;
	int time;
};
std::queue<_qt> Q;
int visited[50 + 2][50 + 2];

void input()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &board[i][j]);
			if (board[i][j] == 2) {
				V.push_back({ i, j });
				board[i][j] = 0;
			}
			else if (board[i][j] == 1) wall++;
		}
	}
	v_cnt = V.size();
	zeros = N * N - wall;
}

void put_virus()
{
	// init
	Q = {};
	memset(visited, -1, sizeof(visited));

	for (int i = 0; i < M; i++) {
		int vx = V[choice[i]].x;
		int vy = V[choice[i]].y;
		board[vx][vy] = 2;
		Q.push({ vx, vy, 0 });
		visited[vx][vy] = 0;
	}
}


int BFS()
{
	int time = 0;	// 0초만에 퍼져버리는 경우가 있을 수 있다. 더 클 때만 최댓값 갱신하게 해줬으므로 0으로 초기화 해야함
	int cnt = M;	// 이미 M개의 바이러스를 고른 상태

	// dir
	int dir_x[4] = { 0, 0 ,1, -1 };
	int dir_y[4] = { 1, -1, 0, 0 };

	while (!Q.empty()) {
		_qt data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
			if (visited[nx][ny] >= 0) continue;
			if (board[nx][ny] == 1) continue;
			Q.push({ nx, ny, data.time + 1 });
			visited[nx][ny] = data.time + 1;
			if (time < data.time + 1) time = data.time + 1;	// 시간 갱신
			cnt++;	// 채운 빈칸 수
		}
	}
	if (cnt == zeros) return time;
	return -1;
}




void undo_virus()
{
	for (int i = 0; i < M; i++) {
		int vx = V[choice[i]].x;
		int vy = V[choice[i]].y;
		board[vx][vy] = 0;
	}
}


void DFS(int n, int s)
{
	if (n == M) {
		put_virus();
		int time = BFS();
		undo_virus();
		if (time == -1) return;
		if (ans > time) ans = time;
		return;
	}
	
	for (int i = s; i < v_cnt; i++) {
		choice[n] = i;
		DFS(n + 1, i + 1);
	}
}


int main()
{
	input();
	DFS(0, 0);	// V.size, 몇 번 뽑았는지 
	if (ans == 0x7fffffff)printf("%d\n", -1);
	else printf("%d\n", ans);
	return 0;
}

어떤 값으로 초기화해야할지 항상 생각하자.

바이러스가 퍼지기 위한 최소 시간을 구해야하 하는데, BFS 탐색 중에는 맵 전체에 바이러스가 퍼져야 하기 때문에, data.time 중 가장 큰 값을 선택하여 리턴해주어야 한다. 

 

BFS 탐색 시에 0값이 나올 수 있을 것이라고 생각해서 time = -1 로 초기화하였는데, 아예 Q 루프를 들어가지 못하는 경우가 있을 수 있다. (바이러스를 고르는 동시에 다 퍼져버리는 경우) 이때는 time = 0 값을 리턴해야 한다. (이미 다 퍼져버린 것임, 맵 전체에 퍼뜨릴 수 없는 것이 아님) 

따라서 time의 초기값은 -1이 아니라 0이되어야 한다. 

---

연구소를 풀고 좋아하는 지난날의 나..

#include <cstdio>
#include <vector>
#include <queue>
int N, M;
int area[50 + 10][50 + 110];
int choice[10 + 2];
int visited[50 + 10][50 + 10];
int ans = 0x7fffffff;

struct _st
{
	int x;
	int y;
	int t;
};

std::vector<_st> V;

void input(void)
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &area[i][j]);
			if (area[i][j] == 2) {
				V.push_back({ i, j, 1 });
			}
		}
	}
}


void init(void)
{
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (area[i][j] == 1) {
				visited[i][j] = -1;
			}
			else visited[i][j] = 0x7fffffff;
		}
	}
}



void BFS(void)
{
	// 조합으로 뽑은 바이러스 좌표 M개 큐에 담아줌
	std::queue<_st> Q = {};
	for (int i = 0; i < M; i++) {
		int vx = V[choice[i]].x;
		int vy = V[choice[i]].y;
		int vt = V[choice[i]].t;
		Q.push({ vx, vy, vt });
		visited[vx][vy] = vt;	// 바이러스 좌표 방문처리 
		//printf("%d %d %d\n", Q.back());
	}

	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		// 상태발전
		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];
			int nt = data.t + 1;
			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1 || visited[nx][ny] == -1) continue;
			if (visited[nx][ny] <= nt) continue;
			visited[nx][ny] = nt;
			Q.push({ nx, ny, nt });
		}
	}
}


int get_min_days(void)
{
	int min_days = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			min_days = (min_days < visited[i][j]) ? visited[i][j] : min_days;
		}
	}
	if (min_days == 0x7fffffff) return 0x7fffffff;
	return min_days - 1;
}


void Combi(int n, int s)
{
	if (n == M) {
		init();
		BFS();
		int tmp = get_min_days();
		ans = (tmp < ans) ? tmp : ans;
		return;
	}
	for (int i = s; i < V.size(); i++) {
		choice[n] = i;
		Combi(n + 1, i + 1);
	}
}



int main()
{
	input();
	Combi(0, 0);
	if (ans == 0x7fffffff) printf("%d\n", -1);
	else printf("%d\n", ans);
	return 0;
}

으어어어 나도 이제 골드4 내 힘으로 풀 수 있다 ! 야호><

 

// input( ) 함수

데이터를 입력받을 때 바이러스를 놓을 수 있는 칸(area[i][j] == 2)의 좌표를 따로 벡터에 받아주었다.

 

 

// Combi( ) 함수

이 문제는 바이러스를 놓을 수 있는 칸에 바이러스를 무조건 놓는 것이 아니라, 그 중 M개를 선택해서 놓아야 한다. 

이 조건을 보고 "조합"을 생각했다. 

그리고 M개를 선택할 때 마다 BFS 함수를 호출하여 해당 좌표들에 바이러스를 놓았을 때 걸리는 최소 시간을 탐색해 주도록 하였다.

그리고 get_min_days 함수를 호출하여 만약 그 리턴값(최소 시간 )이 ans보다 작으면 갱신하도록 구현했다. (모든 조합의 수 중에서 최소값을 구해야 하기 때문)

 

 

// init( ) 함수

BFS를 돌릴 때 마다 방문 배열을 초기화해준다. 이때, 벽(area[i][j] == 1)이면 어차피 못 가기 때문에 -1로 바꿔준다. 그리고 "최소 시간"을 반환해주어야 하기 때문에 0x7fffffff로 초기화해준다. 

 

 

// BFS( ) 함수

이 함수는 이전 문제인 토마토랑 거의 흡사하다. 동시에 세 구역에서 바이러스가 퍼져야하기 때문에, 조합으로 뽑은 M개의 숫자를 인덱스로 하는 벡터의 원소를 큐에 삽입했다. 그리고 전부 방문처리 해주었다. 이제 해당 좌표들을 시발점으로 탐색을 해 나아갈 것이다. 

한편 이때에도 구현의 편의성을 위해 (비록 바이러스를 놓은 위치이기 때문에 퍼뜨리는데 0시간이 걸리지만) 방문 배열을 1로 놓아주었다. 

 

 

// get_min_days( ) 함수

BFS 함수를 실행 한 후 만들어진 방문 배열을 탐색하면서 만약 방문 배열의 원소값이 min_days = 0 값 보다 크면 갱신한다. 이 때 더 큰 값으로 갱신하는 이유는 어쨌든 모든 연구소에 바이러스가 퍼져야하기 때문이다. 그래서 가장 늦게 퍼지는 바이러스를 기준으로 생각해야 한다. 

그런데 만약, min_days가 0x7fffffff이면 바이러스가 퍼지지 않은 지역이 있다는 의미이다(해당 좌표에 바이러스가 퍼졌다면 초기값이 아니라 갱신되었어야 함). 따라서 이때는 리턴도 0x7fffffff으로 해주고, 그렇지 않고 바이러스가 모두 퍼져서 정상적으로 최솟값을 갱신했을 경우엔 min_days - 1을 리턴해준다. (바이러스가 퍼지기 시작할 때를 1시간으로 놓고 구현했기 때문)

이때, 리턴해주는 위의 값은 "T.size()CM개의 조합의 수 중 1개"를 탐색한 결과이다. 따라서 BFS를 돌릴때 마다 해당 함수를 같이 선언해주고, 모든 조합의 수 중 가장 작은 값을 선택하기 위해서 Combi함수에 ans = (tmp < ans) ? tmp : ans; 와 같은 비교문을 넣어주었다. 

 

 

// main( ) 함수

ans가 0x7fffffff이면 모든 조합의 수를 다 돌아도 연구소 전체에 바이러스를 퍼뜨릴 수 없는 것이므로 -1을 출력한다. 아니면 갱신한 ans를 출력해준다.