👿2636번. 치즈_다시 풀자. : 240329

최근 풀이 : 240329 -> 오래 걸림.

키워드 : 틀림.

• 틀린 풀이
  : 아래 풀이로 진행할 경우. 문제가 있다.

#include <iostream>
using namespace std;

#include <vector>
#include <queue>

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


int bfs(int _y, int _x)
{
	vector<pair<int, int>> temp;

	int num = 0;
	queue<pair<int, int>> q;
	q.push(make_pair(_y, _x));
	check[_y][_x] = true;

	// 상하좌우
	vector<pair<int, int>> dir =
	{ {-1,0} ,{1,0} , {0,-1} , {0,1} };

	while (!q.empty())
	{
		pair<int, int> curVer = q.front();
		q.pop();
		check[curVer.first][curVer.second] = true;

		for (int i = 0; i < 4; ++i)
		{
			// 0일 경우에 넣고, 
			int nextY = curVer.first + dir[i].first;
			int nextX = curVer.second + dir[i].second;


			// 범위 체크 
			if (nextY < 0 || nextY >= n
				|| nextX < 0 || nextX >= m)
			{
				continue;
			}
			// 방문 체크 
			if (check[nextY][nextX] == true)
			{
				continue;
			}

			if (v[nextY][nextX] == 0)
			{
				q.push(make_pair(nextY, nextX));
				check[nextY][nextX] = true;
			}
			else if(v[nextY][nextX] == 1)
			{
				++num;
				v[nextY][nextX] = 0;
				check[nextY][nextX] = true;

				//vector에다가 기록한다음에 종료 전에 
				// check 변수 원복하자.
				temp.push_back(make_pair(nextY, nextX));
			}
		}
	}

	for (int i = 0; i < temp.size(); ++i)
	{
		int y = temp[i].first;
		int x = temp[i].second;
		check[y][x] = false;
	}

	return num;
}

int main()
{
	// 1인 부분을 지우고 
	// 전부 지우는 것이 아니라. 

	// 0인 부분 부터 진행해야 한다. 
	// 그러다가 인접한 부분에서 1 발견 하면 
	// 0으로 변경하고 뛰쳐 나오고, 방문 처리 해당 시퀀스에서는
	// 방문 처리되면 들어가지 못하자.

	// 방문 처리된 정점을 통해서는 인접 시퀀스 진행 못하게 막자.

	cin >> n >> m;
	v.resize(n, vector<int>(m));
	check.resize(n, vector<bool>(m, false));

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			cin >> v[i][j];
		}
	}
	int num = 0;
	int cnt = 0;
	// 불변수 만들어서 이미 들어간 정점에 관해서 할 필요 없다.

	// 여러번 순회하는 거를 이중 포문이랑 bfs 
	// 불변수 체크하는 방식으로 들어가면 카운팅 

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			if (check[i][j] == false)
			{
				num = bfs(i, j);
				if (num != 0)
				{
	
					++cnt;
					cout << num << endl;
				}
			}
		}
	}

	

	cout << "result" << " ";
	cout << cnt;
	//cout << bfs(0, 0);
}

• -> 이 코드로 하면 , 방문 체크로 인해
  

• 출력하면
  아래처럼 나오는데 4 , 20 , 3이 의미하는 것은 바로 옆에 2번째 그래프를
  한번에 탐색하는 것이 아니라....
  

• -> 이것처럼 나눠서 탐색 한거다.
  : 검정색은 비어있는 부분까지 한번에 진행한 것이다.
  

• 어떤 생각이 잘못되었다면 , 방문체크는 오로지 bfs만 진행해야 한다.
  : 왜냐하면 2번째 bfs 돌때, 여기서 바로 뛰쳐 나오게 된다.
  

최종 코드 : 240329

• 방문체크는 bfs 만 하고 , bfs 는 2중 for문으로 처리하는 코드로 변경함.
  -> 통과...

---

최종 코드

https://www.acmicpc.net/source/share/918889c66f1c4ace9ed54fbfccd2c20b

• 결과
  

개선해야 할 점.

1) 번 : 풀이전략으로 불가능할 때

• 내 풀이전략으로 한번 입력 예제를 가지고 진행을 했는데,
• 절대 나올 수 없는 구조라면? 다른 풀이전략으로 접근 해야함.

2) 번 : 모든 컨테이너의 원소를 확인하는 것이 아님.

• 원소 확인하는 방법으로는 안되는 문제임.

풀이전략

• 기준을 원소가 1인 부분을 기준으로 해서 인접한 부분을 확인하는 방식으로 했는데
  이렇게 하게 되면, 가운데 , 노란색 부분에 대한 처리를
  어떻게 할 것인가에 대한 예외가 발생함.
  
  -> 고민하는 시간이 많이 걸렸지만, 스스로 해결하지는 못함.

이렇게 하자.

• 기준을 바깥쪽 0인 부분 딱 한개로 해서 진행하자.
  원소가 0인 부분을 하면 안되고!
  -> 0인부분을 확인해서 인접한 부분을 확인하게 될 경우, 노란색 부분도 처리가 됨.
  --> 겉에만 확인하기 위해서, 인접한 부분에서 1을 만나면, 바로 반환해버리자.
  이렇게 생각을 하게 되면,
  
  ---> 바깥면만 확인을 하게 될 것임.