16234 - 인구 이동

문제

코드

#include <bits/stdc++.h>
using namespace std;

int n,r,l,cnt,sum;
int a[54][54];
int visited[54][54];
vector<pair<int,int>> v;
const int dy[4] = {-1,0,1,0};
const int dx[4] = {0,1,0,-1};

void solve(int y, int x, vector<pair<int,int>> &v){
	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 >= n || visited[ny][nx]) continue;
		if(abs(a[ny][nx] - a[y][x]) >= l && (abs(a[ny][nx] - a[y][x]) <= r)){
			visited[ny][nx] = 1;
			sum += a[ny][nx];
			v.push_back({ny,nx});
			solve(ny,nx,v);
		}
	}
}

int main(){
	cin >> n >> l >> r;
	for(int i = 0; i <n; i++){
		for(int j = 0 ; j < n; j++){
			cin >> a[i][j];
		}
	}
	
	while(1){
		bool flag = 0;
		fill(&visited[0][0], &visited[0][0] + 54*54, 0);
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(!visited[i][j]){
					v.clear();
					visited[i][j] = 1;
					sum = a[i][j];
					v.push_back({i,j});
					solve(i,j,v);
					if(v.size() == 1)continue;
					for(pair<int,int> b : v){
						a[b.first][b.second] = sum / v.size();
						flag = 1;
					}
				}
			}
		}
		if(!flag) break;
		cnt++;
	}
	cout << cnt << '\n';
}

풀이

모든 좌표를 돌아보는데 한번 좌표가 시작된 지점과 조건에 부합하는 연결된 지점을 잘 골라내야한다.
방문을 한번도 하지 않은 지점을 시작으로 조건에 맞는 연결된 지점을 모두 탐색한다.
입력한 l과 r 값 사이의 차이를 가진 값을 방문하는데 방문한다면
그 값을 sum에 추가 시키고 해당 좌표를 vector에 넣는다.
이렇게 탐색이 종료되면 이는 연결된 연합 1개가 된다.
반복문이 종료되고 주어진 vector와 sum으로 a[i][j]값을 변경해주고
다시 탐색을 시작한다. 만약 탐색해서 변화가 없다면 break하고 출력하면 된다.

결과

후기

처음에 든 생각은 한 지점을 기준으로 4곳을 둘러보는데 반대로 이 지점을 탐색하는 경우는 어떻게 해야하나 고민하다가 너무 어렵게 빠졌다.
그냥 탐색이 실행됨과 동시에 로직을 실행시키면 되는 문제였다.
알고리즘 자체는 어렵지 않았지만 로직을 생각해내는 것이 어려웠다.
골드 5라니까 조금 그렇다. 한 골드 3,4는 줄만하다고 생각한다.