[백준][dfs] 16234 인구 이동 c++ 구현

목차

https://www.acmicpc.net/problem/16234

문제

 

문제 구현 방향

종료 조건이 약간 까다로운 문제였다. 그 전 배열과의 비교를 통해 변화가 없을 때 종료 시키면 된다.

범위가 작기 때문에 탐색은 dfs를 통해 반복해서 진행해 주어도 시간 초과가 나지 않는다.

 

 

코드 구현

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

int dx[4] = {0, 0, -1, 1};
int dy[4] = { 1, -1, 0, 0 };
int board[100][100] = { 0 };
int ex[100][100] = { 0 };
int visit[100][100] = { 0 };

vector<pair<int, int>> v; 
vector<int> adj[100];
int N, L, R, cnt=0;


void dfs(int x, int y) {    //dfs탐색 시작
	visit[y][x] = 1;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || nx > N - 1 || ny <0 || ny > N - 1)
			continue;
		if (abs(board[y][x] - board[ny][nx]) < L || abs(board[y][x] - board[ny][nx]) > R)  // 범위가 넘어갈 경우 skip
			continue;
		if (visit[ny][nx])  //방문했을 경우 skip
			continue;
		v.push_back({ nx, ny });  //연합할 좌표 저장
		dfs(nx, ny); 
	}
}

void clear() {    //방문 초기화 함수
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			visit[i][j] = 0;
		}
	}
}

int check() {  //전이랑 비교해서 변화가 없을 시 강제 종료하는 함수
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (board[i][j] != ex[i][j]) 
				return 0;
		}
	}
	return 1;
}
int main() {
	cin >> N >> L >> R;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
			ex[i][j] = board[i][j];
		}
	}

	while (true) {
		clear();   //초기화 함수
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!visit[i][j]) {
					v.clear();  
					v.push_back({ j, i });   
					 dfs(j, i);  
					 int sum = 0;  
					 if (!v.size())
						 continue;
					 for (auto k : v)
						 sum += board[k.second][k.first];  
					 sum /= v.size();
					 for (auto k : v)
						 board[k.second][k.first] = sum;   //연합 인구로 바꾸어줌
				}
			}
		}
		if (check()) 
			break;
		for (int i = 0; i < N; i++) {   // 전 배열 저장
			for (int j = 0; j < N; j++) {
				ex[i][j] = board[i][j];
			}
		}
		cnt++;  
	}

	cout << cnt;

}