[BOJ]14502번: 연구소 (c++)

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

14502번: 연구소

 

 

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

using namespace std;

template<typename T>
using double_v = vector<vector<T>>;

struct pos {
	int x, y;
};

int N, M;
const int NEW_WALL = 3;
enum {LAND, WALL, VIRUS};
int dr_x[] = { 0, 1, 0, -1 };
int dr_y[] = { 1, 0, -1, 0 };
vector<pos> virus;
vector<pos> land;

// bfs로 새로 퍼진 바이러스 개수 구하기
int bfs(double_v<int> test_lab)
{
	// 큐에 바이러스 벡터의 위치값들 push
	queue<pos> q;
	for (int i = 0; i < virus.size(); ++i)
	{
		q.push(virus[i]);
	}

	int virus_cnt = 0;
	while (!q.empty())
	{
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		
		// 4방향 탐색
		for (int i = 0; i < 4; ++i)
		{
			int nx = x + dr_x[i];
			int ny = y + dr_y[i];

			// 범위를 벗어나면 continue
			if (nx < 0 || nx >= N || ny < 0 || ny >= M)
			{
				continue;
			}

			// 다음 위치가 빈 칸일 때, 바이러스 카운팅 후 큐에 push
			if (test_lab[nx][ny] == LAND)
			{
				++virus_cnt;
				test_lab[nx][ny] = VIRUS;
				q.push({nx, ny});
			}
		}
	}
	return virus_cnt;
}

// dfs로 벽 3개 만들기
int dfs(double_v<int> &lab, int cnt, int strt)
{
	/*
		벽 3개가 새로 만들어지면
		해당 조건에서 새로 퍼진 바이러스 개수 리턴
	*/
	if (cnt == NEW_WALL)
	{
		return bfs(lab);
	}

	// land 벡터를 탐색하며 저장된 위치값으로 벽 만들기
	int min_virus = 987654321;
	for (int i = strt; i < land.size(); ++i)
	{
		lab[land[i].x][land[i].y] = WALL;
			
		// 다음 인덱스부터 탐색하는 dfs재귀함수 호출. 
		// 최소값 구하기
		min_virus = min(dfs(lab, cnt + 1, i + 1), min_virus);
			
		lab[land[i].x][land[i].y] = LAND;
	}
	return min_virus;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	cin >> N >> M;
	double_v<int> lab(N, vector<int>(M));

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			cin >> lab[i][j];

			// 빈 칸일 때 : land벡터에 위치값 push
			if (lab[i][j] == LAND)
			{
				land.push_back({ i, j });
			}
			// 바이러스일 때 : virus벡터에 위치값 push
			else if (lab[i][j] == VIRUS)
			{
				virus.push_back({ i, j });
			}
		}
	}

	/*
		최대 안전 영역 출력
		안전영역 : 초기 빈칸 개수 - 새로 만든 벽 개수 - 퍼진 바이러스 개수

		--> 바이러스를 최소로 퍼지도록 하는 3개의 벽을 만들어야 함.
	*/
	cout << land.size() - NEW_WALL - dfs(lab, 0, 0);

	return 0;
}

 

 

 

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다.
안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

위 문제에서 중점적으로 구현해야할 부분은 저 둘이다. 

 

 

 

1. map이 주어지면 빈칸에 벽을 3개 세워야 한다 --> dfs

빈칸 중에서 벽으로 만들 3개를 골라야 한다.

여기서 dfs구현이 적합함을 알 수 있다. 

또한 빈칸 중에서 고를려면 빈칸 위치 배열이 필요하다. 

입력 받을 때 한번에 해결하자.

//입력 
...
cin >> lab[i][j];

// 빈 칸일 때 : land벡터에 위치값 push
if (lab[i][j] == LAND)
{
	land.push_back({ i, j });
}

...

// dfs로 벽 3개 만들기
int dfs(double_v<int> &lab, int cnt, int strt)
{
	if (cnt == NEW_WALL)
	{
		return bfs(lab);
	}

	// land 벡터를 탐색하며 저장된 위치값으로 벽 만들기
	for (int i = strt; i < land.size(); ++i)
	{
		...	
		// 다음 인덱스부터 탐색하는 dfs재귀함수 호출. 
		dfs(lab, cnt + 1, i + 1);
		...
	}
}

 

 

 

2. 안전영역의 값을 계산하려면 바이러스가 퍼진 후의 개수를 구해야 한다 --> bfs

dfs로도 가능하지만,

여러 바이러스가 닿을 수 있는 빈땅을 한번씩만 찍어서

개수를 구하는 것이므로 bfs가 적합하다.

마찬가지로 큐에 바이러스 위치값을 push하려면

입력받을 때 바이러스 벡터를 만들어야 한다.

//입력 
...
cin >> lab[i][j];

// 바이러스일 때 : virus벡터에 위치값 push
else if (lab[i][j] == VIRUS)
{
	virus.push_back({ i, j });
}

...

// bfs로 새로 퍼진 바이러스 개수 구하기
int bfs(double_v<int> test_lab)
{
	// 큐에 바이러스 벡터의 위치값들 push
	queue<pos> q;
	for (int i = 0; i < virus.size(); ++i)
	{
		q.push(virus[i]);
	}

	int virus_cnt = 0;
	while (!q.empty())
	{
	...
	}
}