최근 풀이 : 240329

알고리즘 종류

: 백트래킹.
-> 관건으로는 모든 인덱스 접근해야 하는데, 2중 for문을 어떻게 작성할 것이냐 이다!

어떻게 풀까?

: 문제를 읽어보면,
1. 3개의 벽을 만들기
2. bfs 돌기이다.

관건은 1번 3개의 벽을 어떻게 만들 것인가?

• 문제를 읽어보면, 2중 for문을 돌면서 재귀형태로 진행해야 한다는 것을 파악할 수 있다.

0 0 0
1 0 0 일 경우 이런식으로 벽을 재귀적으로 세워나가야 한다.

• 1 1 1
  1 0 0
• 1 1 0
  1 1 0
• 1 1 0
  1 0 1
• 1 0 1
  1 1 0
• 1 0 1
  1 0 1
• 1 0 0
  1 1 0
• 1 0 0
  1 0 1

• 나의 경우 그래서 이런식으로 MakeWall 함수를 만들었고, 출력을 통해 확인함.
  - 로직에 대해
  : 타겟 인덱스를 재귀를 돌리면서 벽 만든 후 카운팅 한다음에 복귀해서 원복하는 형태의 코드이다.
  

• 출력 결과
  : 잘못되었다.
  1 1 0
  1 0 1
  다음에는
  1 0 1
  1 1 0 이 나와야 하는데....
  1 0 1
  1 0 1 이 나왔다....
  

• 왜 틀렸을까?
  : 아래의 순환 2중 for문을 보면, 인자로 들어오는 _y와 _x는 원복이 불가하다.
  
  -> 정상적이 결과가 나오게 하려면 2중 for문을 0,0으로 해야 한다는 것을 알 수 있지만.

• 이렇게 변경해야 한다.
  

개선할 점 : 240329

: 2중 for문을 인자로 보낸 값으로 진행하면 결국에는 모든 정점에 대한 탐색이 불가하다.
생각을 잘해야 한다.
-> 잘못된 2중 for문으로 작성하게 되면 계속해서 정점의 인덱스가 커지게 되서, 시작되는 인덱스의 정점을 작은 값으로 할 수 없다는 것을 생각해야 한다.
3개 벽을 쌓을 다음에 원복해서 이전의 정점들을 처리하는 방법에 대해서 고찰을 해야 한다.

• 아래는 예전 내용이고 보지 말자.

---

최근 풀이

: 220909 11:53 ~ 12:53

개선할점.

• 코드가 길어서 구현하고자 하는 함수를
  여러개 만들면서 처리할 기능을 다른 곳에
  작성할 수 있음.
  -> 주화입마에 빠지지 말고, 멘붕 하지 말자.

결론

• 해당 함수를 작성하기 전에 , 주석으로
  미리 기능에 대한 정의를 하고, 필요한 기능만 작성하자.

실수한 부분

http://boj.kr/16c64f66db4141af873fbacf22f94474

: 확산이 모두 완료된 이후에 0인 부분을 계산해야 하는데
, bfs 함수 안에서 0인 부분을 계산해버렸음....

---

알고리즘 분류

: 백트래킹, 완전탐색

최근 코드

• 백트래킹과 bfs 로 품.

#include <iostream>
using namespace std;
#include <vector>
#include <string>
#include <algorithm>
#include <queue>

//09:18
int n, m;
int cnt = 0;
// 상하좌우 
int dx[]{ 0,0,-1,1 };
int dy[]{ -1,1,0,0 };

int res = 0;

void bfs(vector<vector<int>>&_v , int _y, int _x)
{
	//if (_v[_y][_x] == 1)
	//	return;

	queue<pair<int, int>>q;
	q.push(make_pair(_y, _x));

	while (!q.empty())
	{
		int curY = q.front().first;
		int curX = q.front().second;
		q.pop();


		for (int i = 0; i < 4; ++i)
		{
			//상화좌우를 확인함
			int nY = curY + dy[i];
			int nX = curX + dx[i];

			// 테투리 확인
			if (nY < 0 || nY >= n
				|| nX < 0 || nX >= m)
			{
				continue;
			}

			// 조건 확인 
			if (_v[nY][nX] == 0)
			{
				q.push(make_pair(nY, nX));
				_v[nY][nX] = 2;
			}
		}
	}

	
}

// 벽을 3개 세워야 함. 
// 조합하는 방식으로 진행해야 하므로.
// 백트래킹으로 접근해야 함. 

void backTr(vector<vector<int>>&_v )
{
	// 1. 종료문
	if (cnt == 3)
	{
		vector<vector<int>>temp(_v);
		// 여기서 바이러스 확산을 해야함.
		// 2인 값의 상하좌우로 확산시키자. 
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < m; ++j)
			{
				if(temp[i][j] == 2)
					bfs(temp, i, j);
			}
		}

		// 모든 영역 확인 후에 안전영역 몇개 있는지를 확인하자.
		int ccnt = 0;
		// 최대 개수를 확인하자. 
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < m; ++j)
			{
				if (temp[i][j] == 0)
					++ccnt;
			}
		}
		res = max(res, ccnt);
		//cout << "안전 영역 : ";
		//cout << res << endl;
		
		return;
	}

	// 2. 상태값 on off
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			if (_v[i][j] == 0)
			{
				// 벽으로 만듬.
				_v[i][j] = 1;
				++cnt;
				backTr(_v);

				// 원복함.
				_v[i][j] = 0;
				--cnt;
			}
			
		}
	}


}




int main()
{
	cin >> n >> m;

	
	vector<vector<int>>v(n, vector<int>(m));
	vector<vector<bool>>check(n, vector<bool>(m));

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			cin >> v[i][j];
		}
	}

	//바이러스 즉 2가 존재하는 영역에서만 bfs 함수를 호출하게 하자. 
	// 
	
	// 벽을 먼저 세운뒤에 돌려야 함... 
	backTr(v);

	cout << res << endl;
}```

## 참고
: 3번 입력값 넣은 후 20초 뒤에 채점됨.

## 풀이전략 
1. 64개의 칸중에서 3개를 선택하는 모든 경우의 수이므로, 컴비네이션으로 
나타낼수 있음. 시간 복잡도 64C3 이므로
64! / (64 - 3) ! * 3! 
-> 64 * 63 * 62 / 3 * 2 
-> 대충 70 * 70 * 70 = 4900 * 70 => 350 000 이므로 
10 만보다는 적으므로 완전탐색으로 풀어야 겠다고 판단함!

2. 벽을 먼저 세워 둔후에 카운팅이 3이 되었을 때 바이러스가 있는 지점을 
기준으로 해서 바이러스 확산을 함.

- 근데 여기서 생각할 부분이 2 다음에 0 0 0 이 부분을 벽으로 세웠다고 하고, 
바이러스 처리 후에 2 바로 옆 0인 부분이 1로 변경되었으므로 다시 원복 
2 0 으로 만들어야 함. 
-> 일반적인 반복문으로 만들수 없음. 
	- 왜냐하면 3인 부분에서 확산을 한다고 하고, 다시 0으로 놓고, 
    다시 진행해보았자, 이전에 카운팅된 2개의 값은 갱신이 안되기 때문임.

-> 재귀를 해야함.
![](https://velog.velcdn.com/images/kwt0124/post/c1b1f663-93a5-4824-bc3c-e7e4c6f06d3f/image.png)

- 그부분이 여기 코드임
![](https://velog.velcdn.com/images/kwt0124/post/cb071928-2271-4fa1-9a36-6778c815bef3/image.png)

- 카운팅이 3일때 바이러스 확산하는 부분에서 종료문을 때리면, 3번 재귀된 부분에서 첫번째 재귀함수가 마치고 나온 뒤, 맨앞의 인덱스 부분에서 다시 시작하게 됨.

## 코드

#include

using namespace std;

#include
#include

int answer = 0;
int cnt = 0;

//상 하 좌 우
int dx[]{ 0,0,-1,1 };
int dy[]{ -1,1,0,0 };

void dfs(vector<vector>&v, int y, int x)
{
//상하좌우를 확인하고 , 0일 경우에만 진행.
for (int i = 0; i < 4; i++)
{
// 조건 체크
int ny = y + dy[i];
int nx = x + dx[i];

	if (ny >= 0 && ny < v.size()
		&& nx >= 0 && nx < v[0].size())
	{
		// 원소값 확인.
		if (v[ny][nx] == 0)
		{
			v[ny][nx] = 2;

			//변경된 부분에 대해서 처리를 바로 해야하므로
			// 여기에 작성함. 
			// 반드시 해야함.
			dfs(v,ny, nx);
		}

	}

}

}

void MakeWall(vector<vector>&v)
{
if (cnt == 3)
{
//바이러스 2인 지점에서 확산이 시작됨.

	// 카운트 3이 될때마다 처음부터 바이러스 확산해야 하므로
	//복사본을 만들어서 진행하자.
	vector<vector<int>>temp(v);

	for (int i = 0; i < temp.size(); i++)
	{
		for (int j = 0; j < temp[0].size(); j++)
		{
			if (temp[i][j] == 2)
			{
				dfs(temp, i ,j);
			}
		}
	}

	//바이러스 확산 완료 후에 결과값 카운팅 0인 곳을 확인
	int result = 0;
	//바이러스 확산 완료 후에 카운팅하자. 
	for (int i = 0; i < v.size(); i++)
	{
		for (int j = 0; j < v[0].size(); j++)
		{
			if (temp[i][j] == 0)
			{
				result += 1;
			}
		}
	}

	answer = max(answer, result);
	return;
}

for (int i = 0; i < v.size(); i++)
{
	for (int j = 0; j < v[0].size(); j++)
	{
		if (v[i][j] == 0)
		{
			v[i][j] = 1;
			++cnt;

			
			// 앞전에 카운팅 1,2 되기전의 인덱스를 
			// 원복을 해야 하므로
			// 재귀를 해야함.
			MakeWall(v);
			 
             // 이건 아닌듯.. : 뒤에서부터 채워나감.
			//재귀 이므로 언제 끝낼지를 만들어야 함.
			// 카운팅 감산을 여기서 해야, 
			// 맨처음 단계의 재귀 단계 함수에서 진행이 가능함.
			--cnt;
			v[i][j] = 0;
		}

		

	}
}

}

int main()
{
// 1단계
//벽을 먼저 세움.
// 그러다가 카운팅이 3이되면 바로

// 2단계
// dfs로 바이러스를 확산시킴
// 확산하다가 마지막에 도착한다거나,
// 벽을 마주했을 때는 종료

// 3단계 
//벽을 세울때 2차 포문으로 돌리면서 , 카운팅 감소
// 다음 인덱스를 진행하고, 
// 카운팅 3일때 다시 바이러스 확산

int n, m;
cin >> n >> m;

vector<vector<int>>v(n, vector<int>(m, 0));

for (int i = 0; i < n; i++)
{
	for (int j = 0; j < m; j++)
	{
		cin >> v[i][j];
	}
}

// 벽을 설치하자
MakeWall(v);

// 바이러스를 확산하자.

cout << answer;

}