인구이동
백준 16234: 인구이동
풀이
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;
}
}