인구이동


백준 16234: 인구이동

문제보기
Alt text

풀이

DFS를 이용하여 4방향 확인하여 국경선을 연다.

소스코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public static class Node {
		int r, c;

		Node(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}
	static int N, L, R;
	static int[][] map;
	static int[] dr = {-1,1,0,0};
	static int[] dc = {0,0,-1,1};
	static boolean[][] visit;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		L = sc.nextInt();
		R = sc.nextInt();
		map = new int[N][N];
		int cnt = 0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		
		while(true) {
			visit = new boolean[N][N];	//방문배열 초기화
			if(!check()) {	//인구이동이 가능한지 확인
				cnt++;
			}
			else {
				break;
			}
		}
		System.out.println(cnt);
	}
	
	public static boolean check() {
		boolean flag = true;	//인구이동이 불가능하면 true, 이동 가능하면 false
		ArrayList<Node> list;
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(!visit[i][j]) {
					list = new ArrayList<>();
					list.add(new Node(i, j));
					int sum = dfs(i, j, list, 0);
					if(list.size()>1) {	//국경선이 열려있는 나라가 있다면
						change(sum, list);	//인구수 조정하기
						flag = false;
					}
				}
			}
		}
		return flag;
	}
	
	public static void change(int sum, ArrayList<Node> list) {
		int n = sum / list.size();
		for(int i=0; i<list.size(); i++) {
			Node node = list.get(i);
			map[node.r][node.c] = n;
		}
	}
	
	public static int dfs(int i, int j, ArrayList<Node> list, int sum) {
		visit[i][j] = true;
		sum = map[i][j];
		
		for(int d=0; d<4; d++) {
			int nr = i + dr[d];
			int nc = j + dc[d];
			
			if(nr>=0 && nc>=0 && nr<N && nc<N && !visit[nr][nc]) {
				int num = Math.abs(map[i][j]-map[nr][nc]);
				if(L <= num && num <= R) {
					list.add(new Node(nr, nc));
					sum += dfs(nr, nc, list, sum);
				}
			}
		}
		return sum;
	}
}