삼성 코딩테스트 기출_(백준)인구이동

난이도 ★★☆

 

문제출처

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

16234번: 인구 이동

포인트

1. dfs

1-1. 연합할 수 있는 국가를 dfs로 넓혀나간다. 일반 dfs 알고리즘이 visit여부와 map의 범위만 체크한다면, 이 문제에서는 인구의 범위를 체크하는 것만 추가해주면 된다. --> canUnion()으로 구현

1-2. 추후에 인구를 적절히 분배(distribution)할 것을 고려하여, dfs를 진행하면서 단순히 visit[][]=1만 해 줄 것이 아니라, 연합하는 나라의 수와 전체 인구 수를 계속해서 누적해 나가는 것도 필요하다.

 

2. 인구 이동 시 시간 초과 문제

dfs를 다 끝내고 나서 연합한 국가들 간의 인구이동 함수를 실행해준다. 이 때, 시간 초과가 나기 쉽다. 따라서 인구 이동시 for(for)를 해주는 것이 아니라, 애초에 dfs를 하면서 연합했던 국가들의 위치를 vector에 따로 저장해 놓는다. --> unions<pair<int,int>>

 

3. 메인에서 초기화

dfs를 실행할 때마다 visit, 누적인구수, 누적 나라 수 등을 매번 초기화하는 것을 잊지 말자.

 

정답코드

#include <iostream>
#include <vector>

using namespace std;
int N, L, R;
int map[100][100];

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

int ans = 0;//최종 정답
int noOfUnion = 0;//한 번의 인구이동에서 총 몇 개의 연합이 생기는지
int noOfCountry = 0;//한 연합 안에 몇개국이 존재하는지
int population = 0;//한 연합 안에 총 몇 명이 존재하는지
vector<pair<int, int>> unions;//연합국들의 위치 저장 벡터

void initialize() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			visit[i][j] = 0;
		}
	}
}

bool check(int r, int c) {//범위체크
	if (r >= 0 && r < N&&c >= 0 && c < N)return true;
	return false;
}

bool canUnion(int r, int c, int nr, int nc) {//연합가능여부 체크
	if (map[r][c] > map[nr][nc]) {
		int diff = map[r][c] - map[nr][nc];
		if (diff >= L && diff <= R)return true;
	}
	else {
		int diff = map[nr][nc] - map[r][c];
		if (diff >= L && diff <= R)return true;
	}
	return false;
}

void dfs(int r, int c) {

	visit[r][c] = noOfUnion;
	noOfCountry++;
	population += map[r][c];
	unions.push_back(make_pair(r, c));

	for (int i = 0; i < 4; i++) {
		int nr = r + dy[i];
		int nc = c + dx[i];
		if (!visit[nr][nc] && check(nr, nc) && canUnion(r, c, nr, nc)) {
			dfs(nr, nc);
		}
	}
	return;
}

void distribution() {
	int distPopulation = population / noOfCountry;
	for (int i = 0; i < unions.size(); i++) {
		map[unions[i].first][unions[i].second] = distPopulation;
	}
	return;
}

int main() {
	cin >> N >> L >> R;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}
	while (true) {
		noOfUnion = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!visit[i][j]) {
					unions.clear();
					noOfUnion++;
					noOfCountry = 0;
					population = 0;
					dfs(i, j);
					distribution();
				}

			}
		}
		if (noOfUnion == N * N) break; // 한 번의 인구이동으로 인해 생기는 연합의 갯수가 나라의 개수와 같아지면 인구이동 x
		ans++;
		initialize();
	}

	cout << ans << '\n';

	return 0;
}