[백준 16234] 인구 이동

[문제 바로가기]👇

16234번: 인구 이동

💡풀이💡

문제에서 제시하는 조건을 지키면서 그대로 수행하도록 하기! >> 시뮬레이션!

 

인구 이동 순서

1. 국경선 공유하는 두 나라 인구 차가 L이상, R이하이면 국경선 오픈
2. 국경선 열려 있는 나라끼리 연합 구성
3. 연합 나라의 각 인구수 = (연합의 인구수) / (연합을 이루고 있는 칸의 개수)
4. 모든 국경선 닫기
5. 더 이상 인구 이동을 할 수 없을 때까지 위 과정을 반복!

 

 

문제에서 알 수 있는 정보

국경선을 공유한다 → 상하좌우로 인접해 있다.

 

 

1. 입력 받기

	static int[][] world; // 전체 나라 정보
	static int N, L, R;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		L = Integer.parseInt(st.nextToken()); // 국경선 열기 가능한 최저 인구수
		R = Integer.parseInt(st.nextToken()); // 국경선 열기 가능한 최고 인구수
		world = new int[N][N];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<N; j++) {
				world[i][j] = Integer.parseInt(st.nextToken());
			}
		}
	}

 

 

2. 인구 이동 가능한지 확인

2차원 배열을 순회하며 방문하지 않은 나라이면 bfs로 국경을 열 수 있는 나라를 확인

 

📌놓쳤던 부분

문제에서는 열려야 하는 국경선이 모두 열리면, 인구 이동을 시작한다 라고 되어 있어서 

처음에는 국경을 모두 열고 연합인 나라들을 찾았다.

이 경우에는 국경선을 연 방향을 체크해줘야 하기 때문에 3차원 배열을 사용해서 각 나라가 어느 나라와 국경을 열고 있는지를 체크했다. 

 

하지만 굳이 국경선을 모두 열고 난 다음에 인구 이동을 할 필요 없이

국경선을 열면서 열린 나라들끼리(연합) 인구이동을 진행하면 된다. 

나라를 방문할 때 방문했다고 체크를 한다면 아직 방문하지 않은 다른 연합의 나라에서 이미 방문한 나라와 국경을 열려고 해도 이미 방문 했기 때문에 같은 연합으로 판단하지 않는다! >> 3차원 배열을 쓰는 것보다 대략 25% 정도 속도를 줄일 수 있었다!

 

 

전체 흐름

전체 나라 정보를 순회하면서

1) 방문하지 않은 나라이면 bfs 탐색을 한다.

2) bfs 탐색 완료 후 연합된 나라가 1보다 크면(나 말고 더 있으면) 인구 이동 가능체크(isMove=true)

3) 모든 나라를 탐색을 다 했을 때, 인구 이동이 가능하면 인구 이동 횟수 증가

static boolean move() {
	v = new boolean[N][N];
	boolean isMove = false; // 인구 이동이 가능한지 확인
		
	for(int i=0; i<N; i++) {
		for(int j=0; j<N; j++) {
			if(v[i][j]) continue;
			uc = new ArrayList<>(); 
			sum=0; unitedCnt=1;
			bfs(i,j);
			if(unitedCnt>1) isMove = true; // 연합된 나라가 있다면 인구 이동 true
		}
	}
	return isMove;
}

 

 

 

 

 

3. 연합된 나라끼리 인구 이동 - BFS 탐색

BFS 탐색을 하면서 상하우좌로 인접한 나라들을 확인

방문하지 않았고 두 나라의 인구 수 차이가 L이상 R이하이면! queue에 추가

static void bfs(int i, int j) {
	Queue<int[]> q = new ArrayDeque<>();
	v[i][j] = true; // 연합 확인
	q.add(new int[] { i, j }); // BFS 탐색을 위해 queue에 저장
	uc.add(new int[] { i, j }); // 연합인 나라 좌표 저장
	sum += world[i][j]; // 연합 인구 저장

	while (!q.isEmpty()) {
		int[] pos = q.poll();

		for (int d = 0; d < 4; d++) {
			int ni = pos[0] + dr[d];
			int nj = pos[1] + dc[d];

			// 범위를 벗어나지 않고, 방문한 곳이 아니면
			if (0 <= ni && ni < N && 0 <= nj && nj < N && !v[ni][nj]) {
				int gap = Math.abs(world[pos[0]][pos[1]] - world[ni][nj]); //두 나라 인구 수 차 계산
				if (L <= gap && gap <= R) { // 인구이동 가능한 범위 안의 인구 수 차라면!
					v[ni][nj] = true;
					q.offer(new int[] { ni, nj });
					uc.add(new int[] {ni, nj});
					sum += world[ni][nj];
					unitedCnt++;
				}
			}
		}
	}
		
	// 연합 나라에 인구 이동
}

 

4. 연합 나라의 인구 이동

연합을 이루고 있는 각 나라의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수) 이기 때문에 구한 인구수를

저장해놨던 연합 나라의 좌표에 넣어준다.

// 연합 나라에 인구 이동
int movePopul = sum / unitedCnt; // 연합의 인구수
for (int k = 0; k < unitedCnt; k++) {
	int[] country = uc.get(k); // 연합 나라 좌표 가져오기
	world[country[0]][country[1]] = movePopul; // 연합된 각 나라에 연합의 인구수 만큼만 살기
}

 

 

전체 코드

import java.io.*;
import java.util.*;

public class B16234 {
	static int[] dr = { -1, 0, 1, 0 }; // 상우하좌
	static int[] dc = { 0, 1, 0, -1 }; // 상우하좌
	static boolean[][] v; // 연합 확인
	static int sum, unitedCnt; // 연합된 나라 인구수, 연합된 나라 수
	static List<int[]> uc; // 연합된 나라 좌표 저장

	static int[][] world;
	static int N, L, R;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		L = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		world = new int[N][N];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				world[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		int cnt = 0;
		while (true) {
			if(!move()) break;
			cnt++;
		}
		System.out.println(cnt);
		br.close();
	}

	static boolean move() {
		v = new boolean[N][N];
		boolean isMove = false;
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(v[i][j]) continue;
				uc = new ArrayList<>();
				sum=0; unitedCnt=1;
				bfs(i,j);
				if(unitedCnt>1) isMove = true;
			}
		}
		return isMove;
	}

	static void bfs(int i, int j) {
		// 연합 확인
		Queue<int[]> q = new ArrayDeque<>();
		v[i][j] = true; // 연합 확인
		q.add(new int[] { i, j }); // BFS 탐색을 위해 queue에 저장
		uc.add(new int[] { i, j }); // 연합인 나라 좌표 저장
		sum += world[i][j]; // 연합 인구 저장

		while (!q.isEmpty()) {
			int[] pos = q.poll();

			for (int d = 0; d < 4; d++) {
				int ni = pos[0] + dr[d];
				int nj = pos[1] + dc[d];

				// 범위를 벗어나지 않고, 방문한 곳이 아니면
				if (0 <= ni && ni < N && 0 <= nj && nj < N && !v[ni][nj]) {
					int gap = Math.abs(world[pos[0]][pos[1]] - world[ni][nj]); //두 나라 인구 수 차 계산
					if (L <= gap && gap <= R) { // 인구이동 가능한 범위 안의 인구 수 차라면!
						v[ni][nj] = true;
						q.offer(new int[] { ni, nj });
						uc.add(new int[] {ni, nj});
						sum += world[ni][nj];
						unitedCnt++;
					}
				}
			}
		}
		
		// 연합 나라에 인구 이동
		int movePopul = sum / unitedCnt; // 연합의 인구수
		for (int k = 0; k < unitedCnt; k++) {
			int[] country = uc.get(k); // 연합 나라 좌표 가져오기
			world[country[0]][country[1]] = movePopul; // 연합된 각 나라에 연합의 인구수 만큼만 살기
		}
	}
}