16234 인구이동

phoenixKim·2022년 7월 14일
0

백준 알고리즘

목록 보기
39/174

최근 풀이 : 240331

https://www.acmicpc.net/submit/16234/76056661
-> 맞음. 레벌업!!

  • 전략
    : bfs를 통해서 연결된 정점은 하루간만 연합이라고 했다.
    즉 모든 원소에 대해서 순회했을 때 연합이 있따면 카운팅을 한다는 것이다.
    그리고 다시 첫번째 원소부터 마지막 원소까지 동일하게 진행한다는 것이다.

  • 잘못생각한 점
    나는 그냥 인자로 들어오는 visited를 그냥 복사해서 사용하려고 했는데
    이렇게 되면, 하루동안이 아니라, 코드내에서 인접한 정점 중 조건에 만족한 거가 반복적으로 알아서 처리하게 되는 거다.
    -> 문제에서 언급한 하루동안이므로 이부분이 잘못됨.

  • 잘못된 풀이.
    https://www.acmicpc.net/submit/16234/85565817

접근

  1. 모든 정점에 대해 bfs 를 진행하고, bfs 내부에서 queue 에 들어가는 정점이 있을 경우, 서로 평균을 구해야 한다.

  2. 만약에 이러한 경우도 생각할 수 있다.
    : 40의 경우 50-30-30 의 속하지 않는데 , 50정점을 마친 이후 36이 되는데
    이제 40을 타겟으로 할 경우 36 ,36,36 에 대해 조건에 만족하면 저 친구들도 돌수 있다.
    그래서 bfs 내부에서 check 변수를 그대로 유지한 상태에서 진행시키기로 함.

  3. 뭔가 인구 이동된 상황이 한번이라고 발생한다면 계속 인구 이동을 해야하기 때문에
    전체적인 틀을 while문으로 만들었다.

  • check 변수는 모든 정점에 대해 탐색 이후 false로 초기화해서 다시
    인구 이동이 가능한지 확인하는 방식으로 만듦.
    -> 다중 vector를 fill로 하려고 했는데 번잡하다. 그래서 한번 while 돌때마다 처음으로 만들어서 진행하기로 결정함.
  1. bfs 내부에서 평균 구하고, 인구 이동 유무를 반환하자.
    : 요거는 비교적 쉽다. 주의할 점으로는 타겟 정점은 반드시 1개 있는 상태에서
    while문 돌게 하니까. 평균 구하는 vector의 사이즈는 무조건 1이라는 것을
    유념해야 한다.
    마지막에 평균 구하는 vector.size() == 1 이라면 인구 이동이 없다는 것을 의미함.
    : bfs 코드는 위의 정답 링크 참고.

과거 풀이

: 240115

생각의 전환...

  • 위의 결과로 만들어지는 배열은
    20 20 20
    20 20 20
    40 22 10
    일 것이고, 한번 더 인구 이동이 가능함.
    20 20 20
    20 18 18
    18 18 18
    -> 이 가능할 것임.

#include <iostream>
using namespace std;
#include <string>
#include <stack>

#include <vector>
#include <queue>
#include <algorithm>

int n, l, r;

// 진행할 때마다 인구 이동으로 인해
// value 변경될 수  있기 때문에 참조타입으로 함.
bool bfs(vector<vector<int>>& _v)
{
	vector<vector<bool>>visited(n, vector<bool>(n, false));
	// 시작점은 항상 0,0

	queue<pair<int, int>> q;
	q.push(make_pair(0, 0));
	visited[0][0] = true;

	vector<pair<int, int>> dir
		= { {-1,0} , {1,0} ,{0,-1} , {0,1} };

	vector<pair<int, int>> vertex; 
	vertex.push_back(make_pair(0, 0));

	while (!q.empty())
	{
		pair<int,int> target = q.front();
		q.pop();

		//if (visited[target.first][target.second] == true)
		//	continue;
		//// 확정된거는 방문 처리.
		//visited[target.first][target.second] = true;

		// 상하좌우 순회하면서 큐에 넣자.
		for (int i = 0; i < 4; ++i)
		{
			int nextY = target.first + dir[i].first;
			int nextX = target.second + dir[i].second;

			// 범위 조건 처리.
			if (nextY < 0 || nextY >= n
				|| nextX < 0 || nextX >= n)
				continue;

			// 인접 정점 전부 탐색을 하면서 
			// 방문체크 처리만 하자. 
			// 전부다 방문해야 함.
			if (visited[nextY][nextX] == true)
				continue;
			//visited[nextY][nextX] = true;

			// vertex에다가 넣을 때는 
			// 인접 정점과의 value 비교 l <= value <= r인지 확인
			int diff = abs(_v[target.first][target.second]
				- _v[nextY][nextX]);
			if (diff >= l && diff <= r)
			{
				vertex.push_back(make_pair(nextY, nextX));
				visited[nextY][nextX] = true;
				q.push(make_pair(nextY, nextX));

			}
			// l < value < r 아니더라도 진행되어야 함.

		}
	}

	if (vertex.size() != 1)
	{
		int sum = 0;
		// 평균 구하고 적용.
		for (int i = 0; i < vertex.size(); ++i)
		{
			pair<int,int> point = vertex[i];
			sum += _v[point.first][point.second];
		}
		sum /= vertex.size();

		// 평균값을 적용하자.

		for (int i = 0; i < vertex.size(); ++i)
		{
			pair<int, int> point = vertex[i];
			_v[point.first][point.second] = sum;
		}
		cout << sum << endl;
		return true;
	}
	
	
	return false;
}

int main()
{
	cin >> n >> l >> r;

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

	// 인접한 정점들 간의 value 차이를 구해서 
	// l <= value <= r 일 경우에 
	// vector<pair<int,int>> temp 에다가 
	// point 형식으로 삽입하자. 
	// 그러다가 모든 정점 탐색이 완료될 경우
	// 해당 temp 에 삽입된 모든 정점들 간의 평균 값을 구한후
	// 해당 정점의 value를 변경하자. 
	// 그리고 카운팅. -> 인구 이동 발생

	// 이를 반복
	// 하다가 만약에 temp의 size가 없다면 종료! 
	// 카운팅 출력 

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

	//cout << "확인용 : " << endl;
	//for (int i = 0; i < n; ++i)
	//{
	//	for (int j = 0; j < n; ++j)
	//	{
	//		cout << v[i][j] << " ";
	//	}
	//	cout << endl;
	//}

	int ret = 0;
	// 일단 bfs로 할 건데 
	// bfs를 언제 까지 할건지를 판단해야 하기 때문에 
	// bool bfs 형식으로 만들자.
	while (1)
	{
		if (bfs(v) == true)
		{
			++ret;
		}
		else
		{
			break;
		}
		
	}
	cout << ret;

	//cout << "bfs 이후 : " << endl;
	//for (int i = 0; i < n; ++i)
	//{
	//	for (int j = 0; j < n; ++j)
	//	{
	//		cout << v[i][j] << " ";
	//	}
	//	cout << endl;
	//}
}
  • 내가 최근의 만든 위의 코드는 오직 시작점인 0,0 point를 가지고 모든 인접한 정점을
    그냥 딱히 조건없이 방문 하고 있는데, 굉장히 빈틈이 많은 코드임.
  • -> 왜냐하면 나는 상하좌우로 해서 아래의 예시는 통과하지만,

    50 20
    30 40
    일 경우에 20과 40의 경우 인구 이동이 가능하고,
    30 40의 경우에는 인구 이동이 불가하지만, 상하좌우가 먼저 실행되기 때문에 50 -> 30 -> 40을 확인하게 되면서 40의 방문은 true 처리되어서 20 정점을 타겟으로 했을 때, 40 정점으로 방문이 불가능한 상황이 발생한다라는 것을 캐치할 수 있어야 함.

-> 즉 위에서 start 점 하나만으로 모든 정점들을 순회하기에는 굉장히 불합리함.

결론
: 외부에서 for(i ~ n)
for(j ~ n ) if(check[][]) bfs
이러한 순으로 각 정점에 대한 순회 처리 동작으로 접근해야 함.

~240115 이전. ~

체킹을 언제 할 것이냐?

  • 체킹을 큐에서 팝하는 순간에 만들었더니, 30퍼센트에서 틀림
  • 체킹을 큐에서 넣는 순간에 했는지 맞음..

https://velog.io/@kwt0124/bfs-%EB%B0%A9%EB%AC%B8-%EC%B2%B4%ED%81%AC%EB%A5%BC-%EC%96%B8%EC%A0%9C-%ED%95%A0-%EA%B2%83%EC%9D%B8%EA%B0%80%EC%97%90-%EB%8C%80%ED%95%9C-%EA%B3%A0%EC%B0%B0

언제품?

:220910


이전 풀이

: 엄청난 문제가 있음...

간과 한점.
문제를 읽으면서, 인접한 부분에 대한 bfs 에서의 불체크를
그냥 지역변수로 사용했음.
1) 문제를 읽어보고 생각해보자.

10 15 20
20 30 25
xx 22 xxx
7개 구간은 오늘 하루만큼은 인구 이동이 발생함.
그럼 처리안된 40과 10의 경우, 체크 변수가 초기화된 상태에서
진행을 해야 할까?
안됨. 왜냐하면, 적용이 된 시점에서 7개의 마을들은 연합이기
때문에 40이 타겟으로 bfs 진입 할 때도
체크 변수의 값은 그대로 유지가 되어야 함!
-> 나는 계속 갱신된 값이 아닌 초기화 상태에서 진행을 해서
문제가 발생한 것임.
2) 실수
: 연합이 된 그 순간, 즉 하루만큼에 해당하는 원소값만 평균치로
값이 갱신되어야 함.

-> 노란색 쳐져있는 부분으로 처리해서 문제가 됬음.
밑에 처럼 벡터에 넣은 값만으로 변경을 해야 함!

  • 최종 코드

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

int n, l, r;

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

// 4:06
bool bfs(vector<vector<int>>&v , vector<vector<bool>>&check  , int y, int x)
{
	vector<pair<int,int>>vv;

	static int num = 1;
	queue<pair<int, int>>q;
	q.push(make_pair(y, x));
	int sum = 0;
	int cnt = 1;
	check[y][x] = true;
	//sum += v[y][x];
	vv.push_back(make_pair(y, x));
	// 인접한 인덱스 정보를 알아야 함.

	while (!q.empty())
	{
		int curY = q.front().first;
		int curX = q.front().second;
		sum += v[curY][curX];
		q.pop();

		for (int i = 0; i < 4; ++i)
		{
			int nY = curY + dy[i];
			int nX = curX + dx[i];

			// 1. 테두리 체크 
			if (nY < 0 || nY >= n
				|| nX < 0 || nX >= n)
				continue;

			// 불변수 체크 . 중복 진입 방지
			if (check[nY][nX] == true)
				continue;

			// 2. 조건 체크 : 여기서는 l r
			int diff = abs(v[curY][curX] - v[nY][nX]);

			if (diff >= l && diff <= r)
			{
				vv.push_back(make_pair(nY, nX));
				check[nY][nX] = true;
				q.push(make_pair(nY, nX));
				++cnt;
				//sum += v[nY][nX];
				//cout << "들어옴 : " << diff << " " << nY << ' ' << nX << endl;
			}
		}
	}

	int changeValue = sum / cnt;

	// 불변수 체크를 통해 어떤 인덱스에 있는 위치가 
	// 인접해 있는지 알 수 있음. 

	// 이 부분이 잘못됨... 

	//vv
	//for (int i = 0; i < n; ++i)
	//{
	//	for (int j = 0; j < n; ++j)
	//	{
	//		if (check[i][j] == true)
	//		{
	//			v[i][j] = changeValue;
	//		}
	//	}
	//}

	for (int i = 0; i < vv.size(); ++i)
	{
		int yy = vv[i].first;
		int xx = vv[i].second;
		v[yy][xx] = changeValue;
	}


	// 인접한 것이 하나라도 있을 경우에는 true로 반환해야 함.
	if (cnt != 1)
	{
		//cout << "input : " << y << ' ' << x << endl;
		//cout << "output" << num << endl;
		num++;
		//for (int i = 0; i < n; ++i)
		//{
		//	for (int j = 0; j < n; ++j)
		//	{
		//		cout << v[i][j] << " ";
		//	}
		//	cout << endl;
		//}
		return true;

	}
	else
		return false; 

}

// 4:06
int main() 
{
	//하루동안만 연합
	// 그리고 인구 이동을 함. 
	// 두 나라간의 인구차 l 이상 r 이하일 경우
	// 각 칸의 인구 수 :
	// 연합의 인구수 / 연합을 이루고 있는 칸의 개수
	// 연합을 해제하고 국경선을 닫음.
	
	cin >> n >> l >> r;

	// 인접한 부분을 접근해야 하므로
	// bfs로 가야함. 
	// 인접한 부분을 넣은 후에 
	// 계산 처리를 해야 함.

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

	//cout << "before" << endl;
	//
	//for (int i = 0; i < n; ++i)
	//{
	//	for (int j = 0; j < n; ++j)
	//	{
	//		cout << v[i][j] << " ";
	//	}
	//	cout << endl;
	//}

	int rres = 0;
	
	while (1)
	{
		vector<vector<bool>>check(n, vector<bool>(n));

		bool cccheck = false;
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				if (check[i][j] == false)
				{
					if (bfs(v, check, i, j))
					{
						cccheck = true;
					}
				}
				
			}
		}
		
		if (cccheck)
			rres++;
		else
			break;
	}

	
	
	//cout << "after" << endl;
	//for (int i = 0; i < n; ++i)
	//{
	//	for (int j = 0; j < n; ++j)
	//	{
	//		cout << v[i][j] << " ";
	//	}
	//	cout << endl;
	//}

	//cout << "result" << endl;
	cout << rres << endl;


}


내 생각

: 문제를 잘못 이해함.
: 5번 반례를 통해 생각을 다시 해봐야 했다!

첫번째 풀이..


#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

// bfs에서 조건 처리에 사용할 거라서 전역으로 뺌.
int n, l, r;

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

bool bfs(int _y, int _x, vector<vector<int>>& _v)
{
	// 값이 평균값으로 변경되므로 
	// 참조로 처리함. 
	// 변경 후에 또 인접한 것들과의 차이가 
	// l ~ r 만큼의 차이가 생기면 또 평균값 계산을 해야하므로 
	// 인덱스를 기준으로 해서 bfs를 진행함. 
	//int sum{ 0 };

	// l과 r에 있는 것들을 나열하고 ,
	// 평균 처리를 하기위한 갯수를 구해야 하므로 
	// 벡터를 사용함. 
	//vector<int>arr;
	// 삽입할때마다 용량 증대해서 효율성 떨어지는 것을 방지함. 
	//arr.reserve(n * n); 

	vector<pair<int, int>>idx;
	idx.reserve(n * n);

	int sum = 0;
	int cnt = 0;

	// 불변수
	vector < vector<bool>>check(n, vector<bool>(n, false));

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

	idx.push_back(make_pair(_y, _x));

	// 자기자신을 넣어준 후에 시작하자. 
	//arr.push_back(_v[_y][_x]);
	sum += _v[_y][_x];
	++cnt;


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

		q.pop();

		for (int i = 0; i < 4; ++i)
		{
			int nextY = curY + dy[i];
			int nextX = curX + dx[i];

			// 조건처리
			// 1. 인덱스 범위 체크
			// 2. 인접한 놈들끼리의 l ~ r 체크
			// 3. 불변추 처리

			// 1번
			if (nextY < 0 || nextY >= n
				|| nextX < 0 || nextX >= n)
				continue;
			// 3번 
			if (check[nextY][nextX] == true)
				continue;
			// 불체크를 잘못한듯? 
			//if(check[nextY][nextX] == false)
			//	check[nextY][nextX] = true;

			//2번
			int dif = abs(_v[curY][curX]- _v[nextY][nextX]);

			if (dif >= l && dif <= r )
			{
				if(check[nextY][nextX] == false)
					check[nextY][nextX] = true;
				q.push(make_pair(nextY, nextX));
				//arr.push_back(_v[nextY][nextX]);
				sum += _v[nextY][nextX];
				++cnt;
				idx.push_back(make_pair(nextY, nextX));
			}
		}
	}

	int avg = sum / cnt;

	// 모든 idx 를 탐색하면서 인자로 들어온 _v의 원소값을 변경
	for (auto iter : idx)
	{
		_v[iter.first][iter.second] = avg;
	}

	// 인덱스 값을 가지고 있다가 한번에 처리하는 편이 좋을듯? 

	

	if (idx.size() >= 2)
	{
		// 평균값을 구하고 변경해야 함. 
	// 전체를 조건처리 한다기 보다는... 
		cout << "돌려" << endl;
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				cout << _v[i][j] << " ";
			}
			cout << endl;
		}
		cout << "종료 " << endl;

		return true;

	}

	return false;
}


int main()
{
	//10 100 20 90
	//80 100 60 70
	//70 20 30 40
	//50 20 100 10

	// 10 ~ 50 
	//10 100 20/s 90
	//80/ 100/ 60/ 70/
	//70/ 20/ 30/ 40/
	//50/ 20/ 100 10/



	// n by n  크기의 땅이 있음. 
	// r행 c열에 있는 나라에는 a[r][c] 명의 사람이 있음. 

	// 인접한 나라 끼리의 l명이 상 ~ r명 이하 라면
	// 두 나라가 공유하는 국경선을 오픈함. 

	// 10/ 15/ 20/
	// 20/ 30/ 25/
	// 40  22/ 10 

	// 10 15 20 20 30 25 22
	// 25 40 30 47
	// 65 77
	// 142 
	// 142 / 7 : 20 

	// 20 20 20
	// 20 20 20
	// 40 20 10

	// 10 20 10

	// 50 / 3 : 17

	// 20 20 20
	// 20 20 17
	// 40 17 17

	// bfs로 상하좌우 , 인접한 영역의 차이를 확인하자.
	// for문으로 모든 2차원 인덱스를 접근해서 처리해야 함. 
	// 값이 계쏙 변경되므로, 인자 참조를 사용하든 전역을 사용하든

	cin >> n >> l >> r;
	
	// 정사각형을 만듬. 
	vector<vector<int>>v(n, vector<int>(n, 0));
	
	// 입력값. 
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			cin >> v[i][j];
		}
	}
	
	int result = 0;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			//bfs 돌려 
			// 인덱스를 기준으로 해서 돌려야 함. 
			if(bfs(i,j,v))
			{
				++result;
				//참조로 돌리자.
				//bfs(i, j,v);
			}
		}
	}
	cout << result;

	//for (int i = 0; i < n; ++i)
	//{
	//	for (int j = 0; j < n; ++j)
	//	{
	//		cout << v[i][j] << " ";
	//	}
	//	cout << endl;
	//}

}

-> 출력 초과 발생함.

그리고 예제 입력 1,2,3,4는 맞았는데,
5번이 틀림.
-> 아 뭔지 알겟다.

왜 못 풀었냐 ? 에 대해서

: 문제를 잘못 이해함..

  • 내가 푼 풀이는 인덱스 별로 하나씩 지정했을 때 몇번의 그룹이 변경되었는지를 나타내는 것임.

    : bfs 한번 완료 후 평균값으로 변경한 상태에서 하루동안 그 그룹은 연합이라고 한다면? 그럼 여기서 카운팅을 할것이냐?
    그것은 아님

그러면 인접한 상태의 값들은 이미 하루가 지나간 것일까? 에 대한
반례는 5번임.

10 100 20 90
80 100 60 70
70 20 30 40
50 20 100 10

내 생각대로라면 5번 이 나와야함. 하지만 5번 입력의 경우 3이다.

  • 3이 나올수 있는 것에 대해서 생각을 해보면,,,

: 마지막 결과를
30 56 56 50
56 56 55 50
56 55 55 55
55 55 62 55
인데
30 56
56
간의 차이가 26 ( 10 ~ 50) 이다
이게 뭔 뜻이냐면 한번더 진행하라는 것임.

결과

: 문제를 잘못 이해함.
내가 푼 풀이대로 하면 여기서 끝나야 하지만,
내가 마지막에 도출한 결과를 보면 0 , 0 인덱스와 인접한 친구들 간의 차이는 26이다.

두번재


#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

// bfs에서 조건 처리에 사용할 거라서 전역으로 뺌.
int n, l, r;

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

bool bfs(int _y, int _x, vector<vector<int>>& _v)
{
	// 값이 평균값으로 변경되므로 
	// 참조로 처리함. 
	// 변경 후에 또 인접한 것들과의 차이가 
	// l ~ r 만큼의 차이가 생기면 또 평균값 계산을 해야하므로 
	// 인덱스를 기준으로 해서 bfs를 진행함. 
	//int sum{ 0 };

	// l과 r에 있는 것들을 나열하고 ,
	// 평균 처리를 하기위한 갯수를 구해야 하므로 
	// 벡터를 사용함. 
	//vector<int>arr;
	// 삽입할때마다 용량 증대해서 효율성 떨어지는 것을 방지함. 
	//arr.reserve(n * n); 

	vector<pair<int, int>>idx;
	idx.reserve(n * n);

	int sum = 0;
	int cnt = 0;

	// 불변수
	vector < vector<bool>>check(n, vector<bool>(n, false));

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

	idx.push_back(make_pair(_y, _x));

	// 자기자신을 넣어준 후에 시작하자. 
	//arr.push_back(_v[_y][_x]);
	sum += _v[_y][_x];
	++cnt;


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

		q.pop();

		for (int i = 0; i < 4; ++i)
		{
			int nextY = curY + dy[i];
			int nextX = curX + dx[i];

			// 조건처리
			// 1. 인덱스 범위 체크
			// 2. 인접한 놈들끼리의 l ~ r 체크
			// 3. 불변추 처리

			// 1번
			if (nextY < 0 || nextY >= n
				|| nextX < 0 || nextX >= n)
				continue;
			// 3번 
			if (check[nextY][nextX] == true)
				continue;
			// 불체크를 잘못한듯? 
			//if(check[nextY][nextX] == false)
			//	check[nextY][nextX] = true;

			//2번
			int dif = abs(_v[curY][curX] - _v[nextY][nextX]);

			if (dif >= l && dif <= r)
			{
				if (check[nextY][nextX] == false)
					check[nextY][nextX] = true;
				q.push(make_pair(nextY, nextX));
				//arr.push_back(_v[nextY][nextX]);
				sum += _v[nextY][nextX];
				++cnt;
				idx.push_back(make_pair(nextY, nextX));
			}
		}
	}

	int avg = sum / cnt;

	// 모든 idx 를 탐색하면서 인자로 들어온 _v의 원소값을 변경
	for (auto iter : idx)
	{
		_v[iter.first][iter.second] = avg;
	}

	// 인덱스 값을 가지고 있다가 한번에 처리하는 편이 좋을듯? 



	if (idx.size() >= 2)
	{
		// 평균값을 구하고 변경해야 함. 
	// 전체를 조건처리 한다기 보다는... 
		cout << "돌려" << endl;
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				cout << _v[i][j] << " ";
			}
			cout << endl;
		}
		cout << "종료 " << endl;

		return true;

	}

	return false;
}


int main()
{
	//10 100 20 90
	//80 100 60 70
	//70 20 30 40
	//50 20 100 10

	// 10 ~ 50 
	//10 100 20/s 90
	//80/ 100/ 60/ 70/
	//70/ 20/ 30/ 40/
	//50/ 20/ 100 10/



	// n by n  크기의 땅이 있음. 
	// r행 c열에 있는 나라에는 a[r][c] 명의 사람이 있음. 

	// 인접한 나라 끼리의 l명이 상 ~ r명 이하 라면
	// 두 나라가 공유하는 국경선을 오픈함. 

	// 10/ 15/ 20/
	// 20/ 30/ 25/
	// 40  22/ 10 

	// 10 15 20 20 30 25 22
	// 25 40 30 47
	// 65 77
	// 142 
	// 142 / 7 : 20 

	// 20 20 20
	// 20 20 20
	// 40 20 10

	// 10 20 10

	// 50 / 3 : 17

	// 20 20 20
	// 20 20 17
	// 40 17 17

	// bfs로 상하좌우 , 인접한 영역의 차이를 확인하자.
	// for문으로 모든 2차원 인덱스를 접근해서 처리해야 함. 
	// 값이 계쏙 변경되므로, 인자 참조를 사용하든 전역을 사용하든

	cin >> n >> l >> r;

	// 정사각형을 만듬. 
	vector<vector<int>>v(n, vector<int>(n, 0));

	// 입력값. 
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			cin >> v[i][j];
		}
	}

	int result = 0;
	bool end = false;

	while (1)
	{
		end = false;

		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				//bfs 돌려 
				// 인덱스를 기준으로 해서 돌려야 함. 
				if (bfs(i, j, v))
				{
					//++result;
					end = true;
				}
			}
		}

		if (end)
			result++;
		else
			break;
	}

	cout << result;

	//for (int i = 0; i < n; ++i)
	//{
	//	for (int j = 0; j < n; ++j)
	//	{
	//		cout << v[i][j] << " ";
	//	}
	//	cout << endl;
	//}

}

-> 연합 완료된 후에 , 다른 인접한 공간에서 연합된 부분에 접근을 못하게 해야함.....

// 30 과 30으로 변경 후에
30 100 50 50
30 50 50 50
50 50 50 50
50 50 100 50

30 50
50

은 연합하면 안된다는 의미.
// 여기서 그만..

profile
🔥🔥🔥

0개의 댓글

관련 채용 정보