https://www.acmicpc.net/submit/16234/76056661
-> 맞음. 레벌업!!
잘못생각한 점
나는 그냥 인자로 들어오는 visited를 그냥 복사해서 사용하려고 했는데
이렇게 되면, 하루동안이 아니라, 코드내에서 인접한 정점 중 조건에 만족한 거가 반복적으로 알아서 처리하게 되는 거다.
-> 문제에서 언급한 하루동안이므로 이부분이 잘못됨.
모든 정점에 대해 bfs 를 진행하고, bfs 내부에서 queue 에 들어가는 정점이 있을 경우, 서로 평균을 구해야 한다.
만약에 이러한 경우도 생각할 수 있다.
: 40의 경우 50-30-30 의 속하지 않는데 , 50정점을 마친 이후 36이 되는데
이제 40을 타겟으로 할 경우 36 ,36,36 에 대해 조건에 만족하면 저 친구들도 돌수 있다.
그래서 bfs 내부에서 check 변수를 그대로 유지한 상태에서 진행시키기로 함.
뭔가 인구 이동된 상황이 한번이라고 발생한다면 계속 인구 이동을 해야하기 때문에
전체적인 틀을 while문으로 만들었다.
: 240115
#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;
//}
}
-> 즉 위에서 start 점 하나만으로 모든 정점들을 순회하기에는 굉장히 불합리함.
결론
: 외부에서 for(i ~ n)
for(j ~ n ) if(check[][]) bfs
이러한 순으로 각 정점에 대한 순회 처리 동작으로 접근해야 함.
: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이다.
: 마지막 결과를
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
은 연합하면 안된다는 의미.
// 여기서 그만..