https://www.acmicpc.net/problem/14502
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크
www.acmicpc.net
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 00은 빈공간이고 1은 벽이고 2는 바이러스다.
바이러스는 상하좌우로 퍼질수 있고 벽은 통과할 수 없다.
벽을 3개 설치해서 바이러스가 퍼지지 않는 빈공간(0)의 최대 개수를 구해야 하는 문제다.
2.접근방법[알고리즘]
1.추가로 벽(1)을 세개 설치해야한다.
2.벽을 세개 설치 한 뒤 바이러스가 퍼진 결과를 구한다.
3. 그 결과에서 0의 개수를 구해준다.
4. 0의 개수를 저장해주며 벽을 다르게 설치할 때마다 0의 개수를 구하고 최댓값을 출력한다.
이렇게 풀기 위해서
벽을 세개 설치 하는 걸 DFS함수로 구현했다.
벽을 세개 설치하면 그 때 바이러스를 퍼트린 후 0의 갯수를 리턴한다.
DFS를 돌면서 ans변수에 최댓값을 저장해준다.
void DFS(int x, int y, int L) {
if (L == 3) {
//바이러스 BFS 돌고 0 갯수 새기
ans = max(ans, Count());
}
else {
// 벽 만들기 백트래킹
for (int i = x; i < n; i++, y=0) {
for (int j = y; j < m; j++) {
if (arr[i][j] == 0) {
arr[i][j] = 1;
DFS(i, j, L + 1);
arr[i][j] = 0;
}
}
}
}
}2중 for문을 왜 저렇게 쓰는지 이해가 안가면
https://dingcoding.tistory.com/85
백준 15684번 : 사다리 조작 - DFS, 백트래킹, 가지치기의 중요성
https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선
dingcoding.tistory.com
위 글의 3.문제풀이코드 부분에 설명을 보면 좋다.
벽을 설치한뒤 0의 갯수를 구하는 Count 함수를 구현했다.
int Count() {
BFS();
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 0) cnt++;
else if (arr[i][j] == 2) {
//arr배열을 재사용하기위해 BFS 돌아서 바이러스가 퍼진 영역을
//다시 0으로 만들어준다.
arr[i][j] = 0;
}
}
}
//바이러스 초기화 arr 원상태로 만들어줌
for (int i = 0; i < virus.size(); i++)
arr[virus[i].first][virus[i].second] = 2;
return cnt;
}
Count를 다 하고 나면 arr배열에 초기 입력값을 그대로 저장해준다.
3.문제풀이코드 C++
#include <bits/stdc++.h>
using namespace std;
int n, m, arr[10][10], ans;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
vector<pair<int, int> > virus;
queue<pair<int, int > > Q;
// 바이러스 퍼트리는 함수
void BFS() {
for (int i = 0; i < virus.size(); i++) {
Q.push({ virus[i].first, virus[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 nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (arr[nx][ny] == 0) {
//바이러스가 퍼질 수 있는 곳이면 바이러스로 만들어준다.
arr[nx][ny] = 2;
Q.push({ nx,ny });
}
}
}
}
//0 갯수 세는 함수
int Count() {
BFS();
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 0) cnt++;
else if (arr[i][j] == 2) {
//arr배열을 재사용하기위해 BFS 돌아서 바이러스가 퍼진 영역을
//다시 0으로 만들어준다.
arr[i][j] = 0;
}
}
}
//바이러스 초기화 arr 원상태로 만들어줌
for (int i = 0; i < virus.size(); i++)
arr[virus[i].first][virus[i].second] = 2;
return cnt;
}
void DFS(int x, int y, int L) {
if (L == 3) {
//바이러스 BFS 돌고 0 갯수 새기
ans = max(ans, Count());
}
else {
// 벽 만들기 백트래킹
for (int i = x; i < n; i++, y=0) {
for (int j = y; j < m; j++) {
if (arr[i][j] == 0) {
arr[i][j] = 1;
DFS(i, j, L + 1);
arr[i][j] = 0;
}
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
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) {
virus.push_back({ i,j });
}
}
}
DFS(0, 0, 0);
cout << ans << '\n';
}
문제풀이후기
다중 for문을 사용해 벽을 세우는 방법도 있다.
그래도 위 코드처럼 DFS를 이용해서 벽을 세우고 백트래킹해주면
더 간결한 것 같다.
'Algorithm > problem' 카테고리의 다른 글
| 백준 17142번: 연구소 3 - DFS, BFS, 백트래킹 C++코드 (0) | 2022.02.03 |
|---|---|
| 백준 17141번 : 연구소 2 - BFS DFS 백트래킹 응용 문제 (0) | 2022.02.02 |
| 백준 15653번 : 구슬 탈출 4 , C++ 문제풀이 코드 (0) | 2022.02.02 |
| 백준 13913번: 숨바꼭질 4 - BFS, DFS 활용 (0) | 2022.02.02 |
| 백준 13459번 : 구슬 탈출 - BFS C++ 문제풀이코드 (0) | 2022.02.02 |
