[백준 16234] - 인구이동(JAVA)

[문제] 

출처 - https://www.acmicpc.net/problem/16234

16234번: 인구 이동

---

[문제 풀이]

이 문제는 BFS 와 구현을 해야한다. 그래서 다소 어렵게 느껴졌다.

 

• 모든 좌표에 대하여 BFS 탐색을 시작한다.
• 국경선을 공유하는 두 나라의 인구차이 L명 이상 R명 이하면 방문처리를 한다.
• ArrayList를 사용하여 방문한 좌표값을 기록한다.
• BFS 탐색이 끝나면 List에 있는 좌표값을 이용해 각 칸의 인구수를 (연합의 인구수) / (연합을 이루고 있는 칸의 개수) 로 만든다.
• 방문을 초기화 하고 다시 BFS 탐색을 시작한다.
• 움직인 나라가 없으면 BFS를 종료한다.

구현 뿐만아니라 문제를 풀때는 항상 무엇을 해야하는지 글로 정리를 한뒤 문제를 풀면 좀 더 수월하게 해결 할 수 있다.

 

---

[소스 코드]

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

class Pair{
	int x;
	int y;
	
	Pair(int x, int y){
		this.x = x;
		this.y = y;
	}
}

public class Main {

	static final int dx[] = {0,0,1,-1};
	static final int dy[] = {1,-1,0,0};
	static ArrayList<Pair> unionXY = new ArrayList<>();
	static boolean visit[][];
	static int map[][];
	static int n,l,r,cnt;
	static boolean isMove = false;
	
	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());
			}
		}
		
		move();
		
		System.out.println(cnt);
        
	}
	static void move() {
		
		while(true) {
			isMove = false;
			visit = new boolean[n][n]; //새로 BFS 시작할때마다 방문 초기화
			
			for(int i=0; i<n; i++) {
				for(int j=0;j<n; j++) {
					if(!visit[i][j]){
						 bfs(i,j);    //방문하지 않은상태면 BFS 시작
					}				
				}
			}
												
			if(!isMove) break; //국경이동이 없으면 종료.
			else cnt++; //국경이동이 있었다면 일수 추가.
		}
			
	}
	
	static void bfs(int x, int y) {
		Queue<Pair> q = new LinkedList<>();
		q.add(new Pair(x,y));
		visit[x][y] = true;
		unionXY.add(new Pair(x,y));
		
		while(!q.isEmpty()) {
			Pair p = q.poll();
			x = p.x;
			y = p.y;
			
			for(int k=0; k<4; k++) {
				int nx = x + dx[k];
				int ny = y + dy[k];
				
				if(0<=nx && nx<n && 0<=ny && ny<n) {
					if(!visit[nx][ny] && l <= Math.abs(map[x][y] - map[nx][ny]) &&  Math.abs(map[x][y] - map[nx][ny]) <= r) {
						isMove = true;
						visit[nx][ny] = true;
						unionXY.add(new Pair(nx,ny));
						q.add(new Pair(nx,ny));
					}
				}	
			}				
		}	
		
		//BFS 가 끝나면 인구이동 결과 맵에 집어넣기
		int sum = 0;
		for(int i=0; i<unionXY.size(); i++) {
			Pair p = unionXY.get(i);
			 sum += map[p.x][p.y];
		}
		
		for(int i=0; i<unionXY.size(); i++) {
			Pair p = unionXY.get(i);
			map[p.x][p.y] = sum / unionXY.size();
		}
		unionXY.removeAll(unionXY);
	}
}