주의할 점
: 바이러스 확산할때 0인 부분을 2로 바꾼 후
2 인 친구로 다시 확산을 진행해야 하므로
-> 이렇게 재귀로 처리한다고 하면 논리적 으로 맞지 않다. 왜냐하면
-> 순차적으로 2인 구간을 호출하는데, 이전 번호값이 2로 변한다면
이전 구간에서 바이러스 확산을 못하게 되는 문제가 생기기 때문이다.
따라서 코드 변경해야 한다.
몇 번 풀어 봄?
: 2번 //09-24
풀이전략
-
벽을 모두 세운 후에, 바이러스 확산이 진행된다.
-
벽 3개를 어떻게 세우고, 그로 인해 확산되지 않은곳 0인 부분은 카운트 하는 것이다.
-
최대 크기가 8 8이므로 완탐을 해도 시간 복잡도에 무리는 없다.
: 64C3 이므로 64 ! / (64 - 3) ! 3 !
0인 부분에 1인 벽을 설치하자. 총 3번 설치해서 확산을 늦춰야 하므로
(0,1)인 부분에도 설치해보고, (0,2)인 부분에도 설치해보고, 이런식으로 쭈욱
진행하다가 바이러스 확진 안된 부분을 카운팅하자.
어떻게 하면 좋을까?
(0,1)인 부분에 설치 후, 다시 재귀 동작으로 들어간다. 그래야만, 추후에
(0,1)에 설치를 하지않고, 다음 부분에 설치함으로써 완전 탐색이 가능하기 때문이다.
이를 토대로 코드를 짜보면
dfs(??)
{
//벽 설치하는 카운팅
//~~~~
for(int i ~ 세로 길이)
{
for(int j ~ 가로 길이 )
{
if(arr[i][j] == 0)
{
arr[i][j] = 1;
cnt += 1;
//이런식으로 해야만, arr[i][j] 가 0으로 놓고 탐색이 가능한 것이다.
dfs();
arr[i][j] = 0;
cnt -= 1;
}
}
}
}생각해야 할 부분
-
cnt가 3이 될때 바이러스 확산을 시작해야 한다.
-
그리고 벽을 새로 설치 후 다시 바이러스 확산을 해야하는데,
바이러스 확산후의 배열값을 다시 원본 값으로 돌려서 바이러스 확산을 해야하므로 임시 변수 하나를 만들어서 이값으로 바이러스 확산을 진행해야 한다. -
바이러스 확산할때 , 상하좌우로 확산되므로 타겟 지점을 놓고,
이 지점이 확산된다면 또 이 지점을 가지고 확산을 진행하자.
첫번째 코드
- 바이러스 확산을 한번에 진행했는데, 논리적으로 생각하면 타겟 지점에서 상하좌우 확산을 한다. 전염된 곳이 있다면 다시 전염된 곳을 타겟으로 확산하는 방식으로 코드를 변경하자.
-> 이걸로 하면 예시 1번만 맞고 나머지는 틀린다.
파이널 코드
- 확실한 조건은 tmp가 2일 경우에 바이러스 확산을 들어간다는 것이고
- 인접한 부분이 바이러스 확진 되면 그 친구를 가지고 계속해서 확산을 시켜야 한다는 점을 통해 코드를 변경했다.
소스코드
#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
int n, m;
int cnt = 0;
vector<vector<int>>tmp;
vector<vector<int>>v;
int answer = 0;
//상하좌우
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
void virus(int y, int x)
{
//상하좌우를 재귀로 처리하자.
for (int 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 (tmp[ny][nx] == 0)
{
tmp[ny][nx] = 2;
virus(ny, nx);
}
}
}
void backTracking()
{
//바이러스 확산하자.
if (cnt == 3)
{
tmp = v;
//2일 때만 판단해서 virus 함수 호출하자.
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (tmp[i][j] == 2)
{
virus(i, j);
}
}
}
int result = 0;
//바이러스 확산 완료 후에 카운팅하자.
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (tmp[i][j] == 0)
{
result += 1;
}
}
}
answer = max(answer, result);
return;
}
//벽은 1, 바이러스는 2, 빈 공간은 0
//벽을 3개 세우면서 백트래킹 처리하자.
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (v[i][j] == 0)
{
v[i][j] = 1;
cnt += 1;
backTracking();
v[i][j] = 0;
cnt -= 1;
}
}
}
}
int main()
{
//벽 3개를 모두 세운뒤에 바이러스 확산 후에
//min값 계산하자.
cin >> n >> m;
v.resize(n, vector<int>(m));
//0은 빈칸, 1은 벽, 2는 바이러스이다.
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> v[i][j];
}
}
backTracking();
cout << answer;
}