문제 링크
https://www.acmicpc.net/problem/14502
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크�
www.acmicpc.net
접근 방법
위 문제는 벽 3개를 세울 수 있는 모든 경우에 대해 벽을 세운 후 바이러스를 퍼뜨려 안전영역의 최댓값을 구하면 된다.
벽을 3개를 세우는 방법은 백트래킹으로 가능하나 for문을 3중으로 사용하는 것도 가능하다. 필자는 3중 for문을 사용했으며, 취향에 따라 방법을 달리하여도 된다. 벽을 3개를 세운 뒤 바이러스를 퍼뜨리는 방법은 BFS를 사용하면 된다.
1. 일단 main()에서 입력을 받는 동시에 빈 공간의 위치와 바이러스의 위치의 정보를 저장해 두었다.
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
cin >> room[i][j];
if (room[i][j] == 0)
zeros.push_back({ i,j }); //빈공간
else if (room[i][j] == 2)
virus.push_back({ i,j }); //바이러스 초기위치
}2. 3중 for문을 사용하여 벽 3개를 세울 위치를 각각 first, second, third로 받았으며 해당 위치를 map에서 1로 변경 후 bfs를 사용하여 바이러스를 퍼뜨려 바이러스가 퍼진 공간을 cnt로 반환받았으며 안전영역의 수는 아래와 같이 구할 수 있다.
int safe = zeros.size() - 3 - cnt;safe(바이러스가 퍼진 후 안전영역) =
zeros.size()(바이러스가 퍼지기 이전의 안전영역 수) - 3(벽을 새로 세운 공간) - cnt(바이러스가 퍼진 영역)
소스 코드
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
int room[8][8];
vector <pair<int, int>> zeros;
vector <pair<int, int>> virus;
pair<int, int> direction[4] = { {1,0}, {-1,0}, {0,1}, {0,-1} };
int n, m;
int max_ = 0;
int bfs(int x, int y) {
int cnt = 0;
queue < pair<int, int>> q;
q.push({ x,y });
while (!q.empty()) {
auto elem = q.front();
int i = elem.first;
int j = elem.second;
q.pop();
for (int k = 0; k < 4; k++) {
int next_x = i + direction[k].first;
int next_y = j + direction[k].second;
if (0 <= next_x && next_x < n && 0 <= next_y && next_y < m && room[next_x][next_y] == 0) {
q.push({ next_x, next_y });
room[next_x][next_y] = 2;
cnt++;
}
}
}
return cnt;
}
void build_wall(int n, int m) {
for (int i = 0; i < zeros.size(); i++) {
for (int j = i + 1; j < zeros.size(); j++) {
for (int k = j + 1; k < zeros.size(); k++) {
int cnt = 0;
auto first = zeros[i];
auto second = zeros[j];
auto third = zeros[k];
room[first.first][first.second] = 1;
room[second.first][second.second] = 1;
room[third.first][third.second] = 1;
for (auto &elem : virus) {
cnt += bfs(elem.first, elem.second); //바이러스가 퍼진 영역의 수
}
int safe = zeros.size() - 3 - cnt;
max_ = max(max_, safe);
for (auto &elem : zeros) {
room[elem.first][elem.second] = 0;
}
room[first.first][first.second] = 0;
room[second.first][second.second] = 0;
room[third.first][third.second] = 0;
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
memset(room, -1, sizeof(room));
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
cin >> room[i][j];
if (room[i][j] == 0)
zeros.push_back({ i,j }); //빈공간
else if (room[i][j] == 2)
virus.push_back({ i,j }); //바이러스 초기위치
}
build_wall(n, m);
cout << max_ << "\n";
}
개발 환경 : VS 2019
질문, 지적 환영입니다.
'알고리즘 > 백준' 카테고리의 다른 글
| [C++] 백준 2580 스도쿠 (0) | 2020.06.10 |
|---|---|
| [C++] 백준 4195 친구네트워크 (0) | 2020.06.09 |
| [C++] 백준 17779 게리맨더링2 (0) | 2020.05.29 |
| [C++] 백준 17837 새로운 게임 2 (0) | 2020.05.29 |
| [C++] 백준 1520 내리막길 (0) | 2020.05.26 |
