백준 16234 [인구 이동] - JAVA

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

16234번: 인구 이동

 

---

풀이

1. 국경선을 공유하는(인접한 나라)는 인구 차이가 L이상, R이하라면 국경선을 공유할 수 있다.

2. 국경선이 모두 열렸다면 인구이동 시작

   -> 국경을 공유하는 나라들(연합)이 구성이 된다면

 

문제의 핵심은 두 가지라고 생각한다.

(Q1) 연합을 어떻게 구성할 것인가

=> BFS를 통해 연합을 구성한다.

 

(Q2) N개의 연합이 생길 수 있고, N개의 연합이 인구이동을 끝내야 하루가 지나간다.

=> 모든맵을 순회하며 BFS알고리즘을 적용하고, 모든맵을 순회하였는데도 연합이 결성되지 않을때까지 반복한다.

     모든맵을 순회하였을때 하루가 지나간다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Q16234 {
	
	static int N;
	static int L;
	static int R;
	static int arrMap[][];
	static boolean arrVisit[][];
	static int nDay = 0;
	static Queue<Node> q = new LinkedList<Node>();
	static List<Node> comunityList;
	static int row[] = {0, 0, -1, 1};
	static int col[] = {-1, 1, 0, 0};
	
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		
		N = Integer.parseInt(input[0]);
		L = Integer.parseInt(input[1]);
		R = Integer.parseInt(input[2]);
		
		arrMap = new int[N][N];
		arrVisit = new boolean[N][N];
		
		for(int nRow = 0 ; nRow < N ; nRow++) {
			input = br.readLine().split(" ");
			for(int nCol = 0 ; nCol < N ; nCol++) {
				arrMap[nRow][nCol] = Integer.parseInt(input[nCol]);
			}
		}
		
		doMove();
		
		System.out.println(nDay);
	}

	private static void doMove() {
		
		//BFS로 모든 맵을 순회해야한다.
		//BFS한번은 한개의 연합과 같다.
		while(true) {
			boolean nMoveFalg = false;
			arrVisit = new boolean[N][N];
			
			for(int nRow = 0 ; nRow < N ; nRow++) {
				for(int nCol = 0 ; nCol < N ; nCol++) {
					if(arrVisit[nRow][nCol] == false) {
						int nTotalPerson = bfs(nRow, nCol);
						
						if(comunityList.size() > 1) {
							//연합 인구이동
							doComunityMove(nTotalPerson);
							nMoveFalg = true;
						}
					}
				}
			}
			
			
			if(nMoveFalg == true) {
				nDay++;
			}else {
				return;
			}
		}
	}
	
	private static int bfs(int nRow, int nCol) {

		//연합시작지점
		int nTotalPerson = 0;
		comunityList = new ArrayList<Node>();
		q.add(new Node(nRow,nCol));
		comunityList.add(new Node(nRow,nCol));
		arrVisit[nRow][nCol] = true;
		
		while(!q.isEmpty()) {
			Node cur = q.poll();//현재위치
			
			for(int nIdx = 0 ; nIdx < 4 ; nIdx++) {
				int nTargetRow = cur.row + row[nIdx];
				int nTargetCol = cur.col + col[nIdx];
				
				//맵 범위 체크
				if(nTargetRow < 0 || nTargetCol < 0 || nTargetRow >= N || nTargetCol >= N) 
					continue;
				
				//이미 확인한 좌표 체크
				if(arrVisit[nTargetRow][nTargetCol] == true) 
					continue;
				
				//인구이동 가능유무 체크
				int nCurPerson = arrMap[cur.row][cur.col];
				int nTargetPerson = arrMap[nTargetRow][nTargetCol];
				int nDiff = Math.abs(nCurPerson - nTargetPerson);
				
				if(L <= nDiff && nDiff <= R) {
					
					q.add(new Node(nTargetRow, nTargetCol));
					comunityList.add(new Node(nTargetRow, nTargetCol));
					arrVisit[nTargetRow][nTargetCol] = true;
				}
				
			}
			
			nTotalPerson += arrMap[cur.row][cur.col];
		}
		
		return nTotalPerson;
	}

	private static void doComunityMove(int nTotalPerson) {
		int nCalPerson = Math.round(nTotalPerson/comunityList.size());
		
		for(Node node : comunityList) {
			arrMap[node.row][node.col] = nCalPerson;
		}
		
	}

	private static class Node{
		int row;
		int col;
		
		public Node (int row, int col) {
			this.row = row;
			this.col = col;
		}
	}

}