[백준]16234번 : 인구 이동 - 자바(JAVA)

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

16234번: 인구 이동

 

문제 해석

N x N 크기의 땅이 있고 땅은 1x1개의 칸으로 나누어져 있다. (2차원 배열을 사용)

 

각각의 땅에는 나라가 존재하며 r행 c열에 있는 나라에는 A[r][c]명이 살고 있습니다.

 

인접한 나라 사이에는 국경선이 존재하며 인구를 이동시키려고 합니다.

 

인구 이동의 절차

- 인구 이동이 없을 때 까지 반복하면서 진행합니다. (while문 조건)

 

- 국경선을 공유한 두 나라의 인구 차이가 L명 이상, R명 이하라면 국경선을 하루동안 엽니다. (for 문을 통해 검사)

- 모든 나라에 대해 검사를 진행한 후, 인구 이동을 시작합니다. 

- 국경선이 열려있어서 이동 할 수 있다면, 그 나라들을 연합이라고 합니다.

- 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 됩니다. (여기서 소수점은 버립니다.) (연합을 어떻게 확인할것인가)

- 인구 이동이 이루어지고, 모든 연합은 해제되며, 모든 국경선이 닫힙니다.

 

이 때 인구 이동이 며칠 동안 발생하는지 구하시오.

 

입력

첫째 줄에 N, L, R이 주어집니다. 

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어집니다. ( A[r][c]의 값들) 

 

제약조건

1<= N <= 50

1 <= L <= R <= 100

0 <= A[r][c] <=100

인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.

 

출력

인구 이동이 며칠 동안 발생하는지 출력합니다.

 

문제의 풀이전 설계

입력값 받기

우선 입력값 N, L, R에 대해 입력을 받아야하며

이중 for문 (N x N) 번 반복등 통하여 2차원 배열 A[r][c]에 인구수를 입력받습니다.

배열의 이름은 의미가 없는 A가 아니라 의미가 있는 population을 사용하려고 합니다.

 

핵심 기능

인구 이동이 발생하지 않을 때 까지 반복 ( while문 조건) - 인구이동이 이루어 지고 나면 모든 연합 해제, 국경선 닫힘

국경선을 공유하는 나라들을 확인하며 인구 차이가 L명이상 R명 이하라면 국경선을 여는 기능 (for 문을 통해 검사)

국가별 연합을 확인하는 기능

연합한 국가별로 인구수(연합의 총 인원수 / 연합의 수) 분배하는 기능

 

 

풀이하면서 고민해본점

입력은 어떻게 받는것이 효율적일까? (Sacnner vs BufferedReader)

https://junuuu.tistory.com/7?category=968252 

[Java] Scanner 와 BufferedReader의 차이점

출력은 어떻게 하는것이 효율적일까? (System.out.println vs BufferedWriter)

https://blog.naver.com/scyawer/222072629287

자바)System.out.println vs. BufferedReader

 

인구 이동이 발생하지 않을 때 까지 반복 ( while문 조건)에서 조건문은 어떻게 구현할 것인가?

처음에 boolean move = False 로 선언한뒤 만약 두 국가의 인구수 차이가 L명이상 R명 이하라면 True로 설정한다.

while(move) < while문 반복조건 (move = True이면 반복하고 move = False 이면 종료한다.)

 

국경선을 공유하는 나라들을 확인하며 인구 차이가 L명이상 R명 이하라면 국경선을 여는 기능은 어떻게 구현할 것인가?

처음 생각으로는 배열을 for문으로 순회하면서 해당배열의 오른쪽과 아래를 검사하며 국경선을 열지 말지 검사 하려고 했다.

하지만 위의 방법으로 국가별 연합을 확인하는 기능을 구현하기 위해서는 추가적인 3차원 배열이 필요할 것 같았고 그 배열을 통해서 또 연합을 확인해야 하는 과정이 필요하다고 생각했다.

*3차원 배열이라고 생각한 이유는 배열의 행과열을 확인하는 2차원 배열 + 위, 오른쪽, 왼쪽, 아래의 국경선이 열려있는지 확인해주는 배열

 

따라서 3차원 배열 + 다시 연합을 확인해야 하는 과정이 너무 비효율적일것 같아서 다른 방법을 고민해보기로 했다.

국가별 연합을 확인하는 기능을 구현하기 위해서는 국경선이 연결이 되어있는 쪽으로 계속 타고 들어가야 한다고 생각해서 DFS 느낌으로 구현하면 좋을 것 같다고 생각했다.

 

이 방법을 사용한다면

배열이 방문되었는지 확인하는 2차원 배열인 visited[][]배열(초기값은 모두 False)을 만들어야 한다.

 

2중포문으로 population배열을 확인하면서 국경선을 열 수 있다면 계속 타고 들어가면서 검사를 한다. 이 때 재귀함수로 구현해야 할 수도 있으며,  방문을 한 배열은 visited배열에 True로 저장한다.

 

만약 국경선이 연결되어 있다면 연결된 수 만큼 Count를 하고 Sum에 국가의 인구수를 계속 더 하면서 연합의 총 인구수를 저장한다.

 

2중포문으로 population배열을 확인하는데 하나의 행열에서 재귀함수가 종료되면 (연합의 총 인구수 / 연합의 수)를 계산한 값을 모든 연합에 넣어준다.

 

재귀함수는 어떻게 구현하면 좋을까요?

이때 배열이 -1, N에 접근하지 않도록 if문을 통해 제어한다.

visited[i][j] == false 이며 두 국가의 인구수 차이가 L과 R사이 있다면 국경이 열리도록 합니다.

이 방법을 위, 아래, 오른쪽, 왼쪽을 모두 검사하면서 재귀적으로 호출합니다.

 

이때 재귀함수를 호출하면서 이전의 행열들을 저장해놓는다면 그 행열들을 저장해놓은 배열을 연합이라고 볼 수 있으므로 배열을 기준으로 (연합의 총 인구수 / 연합의 수)를 계산한 값을 넣어준다.

 

이 방법을 토대로 2중포문으로 population배열을 확인하면 2차원 배열인 visited[][]배열이 모두 True가 되면 반복문을 종료하고 다시 인구이동이 일어나는지 검사하게 된다

 

반복문이 종료되게 되면 국경선 공유 확인, 국가별 연합 확인, 연합한 국가별로 인구수 분배하는 기능들이 모두 해결된다.

 

 

모든 나라에 대한 검사를 진행한 후 인구 이동을 시켜야 하는데 한 연합에 대해서 이동을 진행하고 다른 연합이 연결된 것을 찾아 이동을 진행한다면 문제가 없을까요?

 

visited배열을 통해 방문되었는지 확인하기 때문에 겹칠일이 없어 문제가 되지 않음

 

 

어떻게 하면 함수화를 깔끔하게 하고 가독성을 높일 수 있을까?

최대한 한가지 기능만 구현하게 하고 함수가 길어지지 않도록 노력하였으며 의미있는 함수명, 변수이름을 부여함.

 

 

 

package algorithm4;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.math.BigInteger;
public class PopulationMove {
	
	static boolean move = true;
	static int totalPopulation = 0;
	static int countCountry = 0;
	static int[][] population = null;
	static boolean[][] visited = null; 
	static ArrayList<int[]> saveUnion = new ArrayList<int[]>();
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); 
		int L = Integer.parseInt(st.nextToken()); 
		int R = Integer.parseInt(st.nextToken());
		
		population = new int[N][N];
		visited = new boolean[N][N];
		for(int i=0; i< N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {				
				population[i][j] = Integer.parseInt(st.nextToken());				
				visited[i][j] = false;
			}			
		}
		int result = 0;
		
		while(move) {
			move = false;			
			visitCountry(N, L, R);			
			if(move == false) {
				break;
			}
			result++;
			resetVisited(N);
		}
		
		bw.write(result + "\n");
		br.close();
		bw.flush();
		bw.close();

	}
	
	static void visitCountry(int N, int L, int R) {
		for(int i=0; i< N; i++) {		
			for(int j=0; j < N; j++) {
				 if(visited[i][j] == false) {
					 openBorder(N, L, R, i, j);
					 movePeople();					 
				 }
				 //초기화
				 countCountry =0;
				 totalPopulation = 0;
				 saveUnion = null;
				 saveUnion = new ArrayList<int[]>();
				 
			}
		}
	}
	
	static void openBorder(int N, int L, int R, int i, int j) {
		countCountry++;
		totalPopulation += population[i][j];
		visited[i][j] = true;
		//연합의 좌표를 저장하는 ArrayList인 saveUnion
		int [] coord = new int[2];
		coord[0] = i;
		coord[1] = j;
		saveUnion.add(coord);
		
		if(i>0) {
			if(visited[i-1][j] == false && checkOpenBorder(i, i-1, j, j ,L, R)) {				
				move = true;
				openBorder(N, L, R, i-1, j);				
			}			
		}
		if(i<N-1) {
			if(visited[i+1][j] == false && checkOpenBorder(i, i+1, j, j, L, R)) {
				move = true;
				openBorder(N, L, R, i+1, j);				
			}
		}
		if(j>0) {
			if(visited[i][j-1] == false && checkOpenBorder(i, i, j, j-1 ,L, R)) {
				move = true;
				openBorder(N, L, R, i, j-1);
			}
		}
		if(j<N-1) {
			if(visited[i][j+1] == false && checkOpenBorder(i, i, j, j+1 ,L, R)) {
				move = true;
				openBorder(N, L, R, i, j+1);
			}
		}		
	}
	
	static boolean checkOpenBorder(int i1, int i2, int j1, int j2, int L, int R) {
		int temp = Math.abs(population[i1][j1] - population[i2][j2]);
		if( temp >= L && temp <= R) {
			return true;
		}
		else {
			return false;
		}
	}
	
	static void movePeople() {
		if(countCountry!= 1) { // 연합이 있다.
			 int eachUnionPopulation = totalPopulation / countCountry;
			 int [] temp = new int[2];
			 //연합을 순회하면서 넣어주기
			 for(int i=0; i<saveUnion.size(); i++) {
				 temp = saveUnion.get(i);
				 population[temp[0]][temp[1]] = eachUnionPopulation;
			 }
		 }
	}
	
	static void resetVisited(int N) {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				visited[i][j] = false;
			}
		}
		
	}
}

 

코드 설명

풀이하면서 고민해본점이 다 반영이 되어있습니다.

우선 main 함수에서 while문을 기점으로 전은 입력을 받는 부분 후는 출력을 하는 부분입니다.

 

while문의 종료조건으로는 move가 true인 동안 돌아가게 되며 move는 처음에 false로 설정되어 있다가 openBorder 메소드에서 만약 두 국가의 인구수 차이가 L과 R사이라면 true로 설정됩니다.

 

while문 안에는 visitCountry 메소드가 호출됩니다.

visitCuntry는 2중 포문을 통해 국가들을 검사하며 만약 방문되지 않았다면(visited[i][j] ==false) openBorder 메소드와 movePeople 메소드를 호출합니다.

 

openBorder메소드는 재귀함수로 위, 아래, 오른쪽, 왼쪽의 인접국가들과 인구수차이가 L과 R사이라면 그 국가를 호출합니다. 호출하면서 countCountry를 증가시키며 totalPopulation에 국가의 인구수를 계속 더합니다. 또한 saveUnion ArrayList를 사용하여 국가의 좌표를 기록합니다. 이렇게 되었을 때 saveUnion에는 연합된 국가의 좌표가 모두 기록됩니다. 

 

openBorder메소드에서 checkOpenBorder메소드를 호출하는데 이는 인접한 국가들의 인구수 차이가 L과 R사이라면 true 그렇지 않으면 false를 반환하는 메소드입니다.

 

movePeople메소드는 saveUnion의 정보와 totalPopulation, countCountry의 정보를 통하여 연합 국가들에 각각 인구를 삽입합니다.

for문을 통해 saveUnion의 모든 좌표를 순회하며 population[i][j] 에 totalPopulation / counCountry의 값을 삽입합니다.

 

visitCountry 메소드가 끝나게 되면 move가 false인지 확인하고 그렇지 않다면 result를 증가시킵니다. 이후에 resetVisited 메소드를 통해 visited[][] 배열을 초기화 하고 다시 반복합니다.