백준 14502 (연구소) c++

문제

14502번: 연구소

n * m 행렬이 주어지면 바이러스가 퍼지지 않게 3개의 벽을세워 최대의 안전지대를 형성하는 것이 문제입니다.

행렬값 0은 안전지대, 1은 벽, 2는 바이러스공간입니다.

바이러스는 상하좌우로 계속 해서 퍼집니다. 

예를들어 다음과 같은 행렬이 주어졌다면

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

이제 벽을 3개 세워 바이러스를 최대로 막아줘야 합니다.

2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

이렇게 벽을 3개 세워 바이러스가 퍼지면

2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

다음과 같이 바이러스가 퍼집니다.

따라서 정답은 0의 갯수인 27이 정답이 됩니다.

 

이 문제의 관건은 어떻게 벽을 3개 세워 0의 갯수를 최대값으로 만드는가? 였습니다.

처음에는 백트래킹 문제로 오해해 계속 해서 벽을 세워 최댓값을 만들어주는 과정을 생각해 보았지만 시간이 너무 많이 걸리고

구현에도 힘이 들었습니다.

 

다시 생각해보는 결국 벽 3개는 주어진 행렬 값이 0인 곳에 모두 세워보고 그 중 최댓값을 구하는게 최선의 방법이라고 생각했습니다.

그럼 어떻게 벽을 세워야 할까?

 

방법은 생각보다 단순했습니다.

제가 생각한 방법은 조합의 방법을 생각했습니다.

처음 행렬을 입력 받을 때 행렬 값이 0인 곳의 위치를 pair 형 벡터에 넣에 저장해두었습니다.

그 다음 "조합" 을 사용하여 벡터에 저장된 곳에서 3개를 선택해 계속해서 행렬을 탐색했습니다.

for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		cin >> arr[i][j];
        if (arr[i][j] == 2)v.push_back({ i, j });
		if (arr[i][j] == 0)z.push_back({ i,j });
		if (arr[i][j] == 1)wall++;	
        temp[i][j] = arr[i][j];
	}
}

입력 부분입니다.

먼저 v벡터에는 바이러스의 위치가 들어갑니다.

z벡터에는 벽을 세울 수 있는 공간들이 들어갑니다. 즉, 0인 부분이 들어가게 됩니다.

wall 변수에는 현재 벽이 고정적으로 세워진 부분들을 셉니다. 즉, 1이면 ++ 해줍니다.

이는 나중에 바이러스가 퍼진후 0의 갯수를 셀때 필요하게 됩니다.

temp배열에는 임의의 똑같은 arr배열이 들어가게 됩니다. 

우리는 temp 배열을 마음대로 수정하면서 정답을 찾게 됩니다.

vector<int>visit(z.size());
visit[0] = 1;
visit[1] = 1;
visit[2] = 1;
sort(visit.begin(), visit.end());
int m = 0;
do {
	for (int i = 0; i < visit.size(); i++) {
		if (visit[i])temp[z[i].first][z[i].second] = 1;
	}
	memset(chk, false, sizeof(chk));
	m = max(m, bfs());
	for (int i = 0; i < visit.size(); i++) {
		if (visit[i])temp[z[i].first][z[i].second] = 0;
	}
} while (next_permutation(visit.begin(), visit.end()));

사실상 핵심부분입니다.

이제 v 벡터에는 0의 위치가 들어가 있을 겁니다. 여기서 3개를 골라 bfs를 진행하고 

그 중 0의 개수가 가장 많은 것이 답이 될것입니다.

저는 0을 고르는 방법을 visit이라는 벡터를 z벡터 size만큼 만들어 visit 백터의 index가 1인 부분만 z벡터에서

선택해 주어 벽을 세웠습니다.

visit 벡터 안에 1의 값들은 next_permutation 함수에 의해 조합하게 됩니다.

조합할 때 마다 bfs를 돌아 m의 값을 갱신해 가장 큰 m의 값이 정답이 됩니다.

int bfs() {
	int cnt = v.size();
	for (int i = 0; i < v.size(); i++)q.push({ v[i].first, v[i].second });
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = dx[i] + x;
			int yy = dy[i] + y;
			if (xx < 0 ||yy < 0 || xx >= n || yy >= m || temp[xx][yy] == 1 || temp[xx][yy] == 2)
				continue;
			if (chk[xx][yy])continue;
			chk[xx][yy] = true;
			q.push({ xx, yy });
			cnt++;
		}
	}
	return m * n - (cnt + wall + 3);
}

bfs 부분입니다. 

먼저 cnt는 현재 바이러스의 갯수 입니다.

그 다음 줄에 바이러스의 위치를 모두 queue에 넣어주고 bfs를 진행해 줍니다.

bfs가 진행될 때 마다 cnt를 ++ 해주어 바이러스의 갯수를 늘려줍니다.

while문을 다 돌면 바이러스가 다 퍼진 상태가 되므로 이제 0의 갯수를 세어주면 됩니다.

먼저 전체 행렬의 크기(n * m) - (바이러스의 갯수(cnt) + 벽의 갯수(wall) + 우리가 선택한 벽의 갯수(3))

이렇게 return하게 되면 0의 크기가 나오게 됩니다.

---

전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
int n, m;
int dx[4] = { 0, 1, -1, 0 };
int dy[4] = { 1, 0, 0, -1 };
int arr[8][8];
int temp[8][8];
vector<pair<int, int>>v;
vector<pair<int, int>>z;
bool chk[8][8];
queue<pair<int, int>>q;
int wall = 0;
int bfs();
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 2)v.push_back({ i, j });
            if (arr[i][j] == 0)z.push_back({ i,j });
            if (arr[i][j] == 1)wall++;
            temp[i][j] = arr[i][j];
        }
    }
    vector<int>visit(z.size());
    visit[0] = 1;
    visit[1] = 1;
    visit[2] = 1;
    sort(visit.begin(), visit.end());
    int m = 0;
    do {
        for (int i = 0; i < visit.size(); i++) {
            if (visit[i])temp[z[i].first][z[i].second] = 1;
        }
        memset(chk, false, sizeof(chk));
        m = max(m, bfs());
        for (int i = 0; i < visit.size(); i++) {
            if (visit[i])temp[z[i].first][z[i].second] = 0;
        }
    } while (next_permutation(visit.begin(), visit.end()));
 
    cout << m;
 
    return 0;
}
int bfs() {
    int cnt = v.size();
    for (int i = 0; i < v.size(); i++)q.push({ v[i].first, v[i].second });
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int xx = dx[i] + x;
            int yy = dy[i] + y;
            if (xx < 0 ||yy < 0 || xx >= n || yy >= m || temp[xx][yy] == 1 || temp[xx][yy] == 2)
                continue;
            if (chk[xx][yy])continue;
            chk[xx][yy] = true;
            q.push({ xx, yy });
            cnt++;
        }
    }
    return m * n - (cnt + wall + 3);
}