[BOJ] 16234번 인구 이동(C++)

풀이 소요시간 : 45분

실수없이 한 방에 풀어서 기분좋아 포스팅을 남긴다.
시뮬레이션 + 탐색이 혼합된 문제를 풀어보는 것은 처음이였던것 같다.
물론 복잡한 난이도는 아니긴 했다.

문제를 구현하다가 3중 반복문이 발생하길래 시간초과가 뜨지 않을까 생각했지만 N = 50 이라는 적은 데이터 수를 보고 괜찮을거라 판단하고 작성했다. 문제 접근 방식은 다음과 같다.

0. Input() 에서 변수와 배열 값을 입력받는다.

1. DFS 를 사용하여 연합 내부를 탐색하고 인구를 이동시킨다.

2. 이동 전 배열과 이동 후 배열을 비교하여 같은지 확인한다.

3. 같다면 이동이 끝난 것이고, 같지 않다면 1 & 2 를 반복한다.

전체 코드

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

int N, L, R;
int Map[51][51];
int Visit[51][51];
int Temp[51][51];

int Cnt = 0; 
int Sum = 0; 
vector<pair<int, int>> Vector; 

int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

void Clear_Visit() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			Visit[i][j] = 0;
		}
	}
}

// Map 과 Temp 가 같으면 true 를 반환한다.
bool Cmp() { 
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (Map[i][j] != Temp[i][j]) return false;
		}
	}
	return true;
}

// Temp 값을 Map 값으로 동기화 시킨다.
void Sync() { 
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			Temp[i][j] = Map[i][j];
		}
	}
}


void Input() {
	cin >> N >> L >> R;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> Map[i][j];
			Temp[i][j] = Map[i][j];
		}
	}
}

void Dfs(int x, int y) {

	for (int i = 0; i < 4; i++) {
		
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx < 1 || ny < 1 || nx > N || ny > N) continue; // 범위 초과
		if (Visit[nx][ny] == 1) continue;					// 방문 전적 있음

		int Gap = abs(Map[x][y] - Map[nx][ny]);
		if (Gap  < L || Gap > R) continue;					// 인구 차이 범위 초과

		Cnt++;						  // 연합 나라 추가
		Sum += Map[nx][ny];			  // 연합 총 인구수 추가
		Vector.push_back({ nx, ny }); // 연합 좌표 저장

		Visit[nx][ny] = 1;
		Dfs(nx, ny);
	}

}


int main() {

	int Move = 0;
	Input();

	while (true) {

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (Visit[i][j] == 0) {
					Dfs(i, j);

					for (int k = 0; k < Vector.size(); k++) {
						// DFS 좌표 갱신
						int x = Vector[k].first;
						int y = Vector[k].second;
						Map[x][y] = Sum / Cnt;
					}
					Vector.clear();

					Sum = 0;
					Cnt = 0;

				}
			}
		}

		Move++; // 이동 횟수 증가

		if (Cmp() == true) {
			cout << Move - 1 << '\n';
			break;
		}

		Sync();
		Clear_Visit();

	}
}