C++ / 14502 / 연구소 ( 브루트포스, 너비 우선 탐색, 백트레킹 )

728x90

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

문제 요약

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었습니다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 합니다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있습니다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지합니다.

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있습니다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 합니다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보겠습니다.

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳 입니다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있습니다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 됩니다.

바이러스가 퍼진 뒤의 모습은 아래와 같아집니다.

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 합니다. 위의 지도에서 안전 영역의 크기는 27입니다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성해야합니다.

문제 풀이

브루트포스 즉 완전탐색으로 풀 수 있는 문제입니다.

1. 지도를 받습니다. 제 코드에선 지도를 직접적으로 변경해야 하기 때문에 원본 지도를 임시로 저장둘 벡터도 만듭니다.

2. 또한 바이러스 부터 bfs로 주변을 1로 바꿔나가야 하기때문에 바이러스 위치를 따로 저장해둡니다.

3. 모든 경우의 수를 완전탐색 해야하는데 저는 콤비네이션 방법을 활용하였습니다.

4. n * m 안에서 0인칸 중에 ( 빈방 인 ) 만들 수 있는 3개의 i, j를 뽑아내서 벡터에 담습니다. 기존에 한개만 뽑던 방식과 다르게 i / m( 열 )과 i % m ( 행 )으로 만듭니다.

5. 뽑아낸 좌표들이 3개가 되면 해당 좌표를 1로 ( 벽으로 ) 만들고, bfs로 바이러스 위치부터 1로 바꿉니다.

6. bfs 를 마치면 남아있는 빈방을 세서 정답 배열에 가장 큰 경우를 저장합니다.

7. 정답을 출력합니다.

주의할 점

콤비네이션을 지금까지는 i 한개씩만 뽑아봤었는데, i, j로 2개씩 뽑아본건 처음이었습니다.

아래 코드 방법으로 하면 1차원 반복문으로 2차원 좌표를 뽑을 수 있습니다.

예를 들어 m = 4라고 가정하고 i = 6이면:

y = 6 / 4 = 1
x = 6 % 4 = 2
즉, (1,2) 좌표가 됩니다.

코드

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

using namespace std;
//vector<vector<int>>v;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
vector<pair<int, int>>v;
bool visit[100][100];
vector<vector<int>>map;
vector<vector<int>>dist;
vector<pair<int, int>>virus;
int n, m, ans;

void bfs(int y, int x)
{
	queue<pair<int, int>>q;

	q.push({ y, x });
	visit[y][x] = 1;
	while (!q.empty())
	{
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny >= n || ny < 0 || nx >= m || nx < 0)
			{
				continue;
			}
			if (visit[ny][nx])
			{
				continue;
			}
			if (map[ny][nx] == 1)
			{
				continue;
			}
			if (map[ny][nx] == 0)
			{
				map[ny][nx] = 2;
			}
			visit[ny][nx] = 1;
			q.push({ ny, nx });
		}
	}
}

void go(int idx)
{
	// 3개의 좌표가 차면
	if (v.size() == 3)
	{
		// 벽세움
		map = dist;
		for (int i = 0; i < 3; i++)
		{
			map[v[i].first][v[i].second] = 1;
		}
		// bfs 돌림
		for (int i = 0; i < virus.size(); i++)
		{
			memset(visit, 0, sizeof(visit));
			bfs(virus[i].first, virus[i].second);
		}
		int temp = 0;
		// 빈칸 갯수 세기
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (map[i][j] == 0)
				{
					temp++;
				}
			}
		}
		ans = max(ans, temp);

		return;
	}
	// 콤비네이션으로 좌표 3개 벡터 만듬
	for (int i = idx; i < n * m; i++)
	{
		int y = i / m;
		int x = i % m;
		if (dist[y][x] == 0)
		{
			v.push_back({ y,x });
			go(i + 1);
			v.pop_back();
		}

	}
}
int main()
{
	cin >> n >> m;
	map.resize(n, vector<int>(m));
	dist.resize(n, vector<int>(m));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> map[i][j];
			dist[i][j] = map[i][j];
			// 바이러스 위치부터 너비우선탐색으로 탐색해야 하기때문에 바이러스 위치 저장
			if (map[i][j] == 2)
			{
				virus.push_back({ i,j });
			}
		}
	}

	go(0);
	cout << ans;
	return 0;
}

예제 1

7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

결과 1

예제 2

4 6
0 0 0 0 0 0
1 0 0 0 0 2
1 1 1 0 0 2
0 0 0 0 0 2

결과 2

예제 3

8 8
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

결과 3