https://www.acmicpc.net/problem/14502
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크
www.acmicpc.net
난이도: solved.ac 골드 4
접근 방법
이 문제는 N과 M의 범위가 적어서 브루트포스 방식으로 풀 수 있다.
따라서 0인 부분 중 3개를 골라 벽을 세우는 모든 경우의 수를 두고 안전영역의 개수를 구했다.
0인 부분의 개수를 n이라고 하면, nC3의 경우의 수를 모두 파악해야 한다.
구현
nC3개의 경우의 수를 만드는 방법은 다음과 같다.
우선, 0인 부분의 좌표를 미리 저장해둔다. 나는 vacant라는 벡터를 만들어 저장했다.
그리고 n개의 사이즈를 갖는 배열을 만드는데 원소는 모두 0으로 두고 마지막 3개만 1로 만든다.
{0,0,0,...,0,0,1,1,1} 처럼.
그리고 위의 배열을 c++의 STL함수 next_permutation에 돌린다.
그러면
0,0,0,0,...,0,1,1,1
0,0,0,0,...,1,0,1,1
0,0,0,0,...,1,1,0,1
...
1,1,0,1,...,0,0,0,0
1,1,1,0,...,0,0,0,0
처럼 나열되는데,
1인 부분의 index를 vacant에서 매칭시켜 벽을 세울 좌표를 지정했다.
벽을 세우는 방법은 이것으로 끝이고 모든 경우에서 바이러스가 있는 위치를 기준으로 BFS 돌리면 된다.
나는 시간을 더 단축시키고자 입력받을 때 바이러스의 위치를 따로 저장해두어 BFS에서 큐에 해당 좌표들이 우선으로 들어가게 했다.
코드
#include <bits/stdc++.h>
using namespace std;
// virus: 입력으로 들어오는 바이러스의 좌표 저장
// vacant: 입력으로 들어오는 0인 부분 좌표 저장
/*
[벽을 세우는 매커니즘]
마지막 3개의 항을 제외한 모든 항이 0이고 마지막 3개 항은 1인 permu라는 배열을
next_permutation 함수에 돌려서 permu[i] = 1인 i를 골라 vacant[i]에서 좌표를 뽑음
(해당 좌표는 배열 wall에 저장함)
그럼 vacant에서 3개의 좌표가 뽑히므로 해당 좌표 자리에 벽을 세움
*/
vector<pair<int, int>> virus, vacant;
int board[8][8], temp[8][8], permu[64], wall[3][2];
// temp: board 배열 복사본
// permu: next_permutation 함수에 돌릴 배열
int dy[4] = { 1,0,-1,0 }, dx[4] = { 0,1,0,-1 };
int N, M, v, empt, ans;
// v: 입력으로 들어오는 바이러스의 개수
// empt: 입력으로 들어오는 0의 개수
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int i, j, y, x;
cin >> N >> M;
for (i = 0; i < N; i++)
for (j = 0; j < M; j++) {
cin >> board[i][j];
if (!board[i][j]) {
// 0인 좌표 저장
vacant.push_back({ i,j });
empt++; // 0의 개수 1 증가
}
if (board[i][j] == 2) {
// 바이러스 좌표 저장
virus.push_back({ i,j });
v++; // 바이러스 개수 1 증가
}
}
// next_permutation에 돌릴 배열 만들기 (끝 3개만 1로 만듦)
for (i = 1; i <= 3; i++)
permu[empt - i] = 1;
// next_permutation 함수 돌리기
do {
// 원본 내용 복사
for (i = 0; i < N; i++)
for (j = 0; j < M; j++)
temp[i][j] = board[i][j];
int idx = 0, e = 0;
while (e < 3) {
if (permu[idx]) {
// 뽑힌 세 곳 좌표 적기
wall[e][0] = vacant[idx].first;
wall[e][1] = vacant[idx].second;
e++;
}
idx++;
}
// 뽑힌 세 곳에 벽 세우기
for (e = 0; e < 3; e++)
temp[wall[e][0]][wall[e][1]] = 1;
int safe = empt - 3; // 현재 0인 영역의 개수
// BFS 과정
queue<pair<int, int>> q;
for (i = 0; i < v; i++)
q.push(virus[i]); // 바이러스의 좌표 queue에 넣음
while (!q.empty()) {
y = q.front().first;
x = q.front().second;
q.pop();
for (i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || ny >= N || nx < 0 || nx >= M)
continue;
if (!temp[ny][nx]) {
// 0인 부분으로 바이러스 전파
temp[ny][nx] = 2;
q.push({ ny,nx });
safe--; // 안전영역 개수 1 감소
}
}
}
if (safe > ans)
ans = safe;
} while (next_permutation(permu, permu + empt));
cout << ans;
}
성능
