문제

BOJ 16234: 인구 이동 https://www.acmicpc.net/problem/16234

풀이

• 인구 이동이 더 이상 없을 때 까지 while 문을 반복해준다.
• bfs 로 들어가서 인접한 국가를 탐색하고 문제 조건에 맞으면 새로운 인구를 구하여 해당 국가들에 적용한다.
  • Stack 을 사용하여 새로운 인구를 각 국가에 적용해준다.
  • 국경을 개방한 국가의 수가 1보다 큰. 즉, townCnt > 1 이라면 isMoveInDay = true; 를 해주어 while 문 을 탈출할 수 있게 처리한다.

코드

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

public class Main {
	
	static int N, L, R;
	static int[][] map;
	static boolean[][] isVisited;
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {1, -1, 0, 0};
	static boolean isMoveInDay; // 이 날에 인구이동이 있었는가??
	
	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());
			
		map = new int[N][N];
		
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int moveCnt = 0; // 인구이동이 몇 번 있었는지 세는 변수
		
		while(true) {
			isMoveInDay = false; // 이 날에 인구이동이 있었는가??
			isVisited = new boolean[N][N];
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					if(!isVisited[i][j]) {
						Stack<Pos> stack = new Stack<>(); // 인구이동 후 새로운 인구를 해당 국가에 넣어주기 위해 해당 국가 좌표를 스택에 넣음
						int newPerson = bfs(i, j, stack); // 새로운 인구 구하기
						// 인구이동 후 새로운 인구를 해당 국가에 넣어주기
						while(!stack.isEmpty()) {
							Pos p = stack.pop();
							
							int x = p.x;
							int y = p.y;
							
							map[x][y] = newPerson;
						}
					}
				}
			}
			
			if(isMoveInDay) { // 이 날에 인구이동이 있었으면 
				moveCnt++;
			} else {
				break;
			}			
			
		}
		
		System.out.println(moveCnt);
	}
	
	static int bfs(int x, int y, Stack<Pos> stack) {
		Queue<Pos> que = new LinkedList<>();
		
		que.add(new Pos(x, y));
		isVisited[x][y] = true;
		int townCnt = 1; // 몇 개의 국가가 국경을 열었는지
		int personSum = map[x][y]; // 연합이 된 국가의 총 인구 수
		stack.add(new Pos(x, y));
		
		while(!que.isEmpty()) {
			Pos p = que.poll();
			
			int curX = p.x;
			int curY = p.y;
			
			for(int t=0; t<4; t++) {
				int nx = curX + dx[t];
				int ny = curY + dy[t];
				
				if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
				
				if(!isVisited[nx][ny] && isRange(curX, curY, nx, ny)) {
					que.add(new Pos(nx, ny));
					isVisited[nx][ny] = true;
					townCnt++;
					personSum += map[nx][ny];
					stack.add(new Pos(nx, ny));
				}
			}
			
		}
		//국경을 열어 연합한 국가의 수가 1보다 크다면 
		if(townCnt > 1) {
			isMoveInDay = true;
		}
		// 새로운 인구 수	
		int eachPerson = personSum / townCnt;
		
		return eachPerson;
	}
	
	// 두 국가 인구 차이가 범위 안에 들어있는지 판단하는 메소드
	static boolean isRange(int x, int y, int nx, int ny) {
		int diff = map[x][y] - map[nx][ny] > 0 ? (map[x][y] - map[nx][ny]) : (map[nx][ny] - map[x][y]);
		if(diff >= L && diff <= R) {
			return true;
		} else {
			return false;
		}
	}
	
	static class Pos{
		int x, y;
		
		Pos(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
	
}

정리

• 인구 이동을 했을 때. 즉, isMoveInDay == true 일 때 만 moveCnt++를 해줘야 한다.