백준 [16234] 인구이동
문제보기
풀이
- 주의사항 : movePopul()마다 ans를 체크하면 안되고 united() 전체가 끝났을 때를 한번으로 세야함
- united() : bfs 방식으로 연합 체크
- movePopul() : 같은 연합끼리 인구이동
소스코드
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int N, L, R, ans;
static int[][] map;
static int[] dx = { -1, 1, 0, 0 };
static int[] dy = { 0, 0, -1, 1 };
static Queue<int[]> queue;
static int[][] visited;
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];
queue = new LinkedList<>();
ans = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
map[i][j] = sc.nextInt();
}
}
while (true) {
visited = new int[N][N];
if (!united()) {
break;
} else {
ans++;
}
}
System.out.println(ans);
}
public static boolean united() {
boolean flag = false;
int idx = 1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int popul = 0;
int cnt = 0;
if (visited[i][j] != 0)
continue;
boolean chk = false;
for (int k = 0; k < 4; k++) {
int x = i + dx[k];
int y = j + dy[k];
if (isRange(x, y) && visited[x][y] == 0) {
int diff = Math.abs(map[x][y] - map[i][j]);
if (diff < L || diff > R)
continue;
flag = true;
queue.add(new int[] { x, y });
visited[x][y] = idx;
popul += map[x][y];
cnt++;
chk = true;
}
}
if (chk) {
popul += map[i][j];
cnt++;
visited[i][j] = idx;
}
while (!queue.isEmpty()) {
int[] q = queue.poll();
for (int k = 0; k < 4; k++) {
int x = q[0] + dx[k];
int y = q[1] + dy[k];
if (isRange(x, y) && visited[x][y] == 0) {
int diff = Math.abs(map[x][y] - map[q[0]][q[1]]);
if (diff < L || diff > R)
continue;
queue.add(new int[] { x, y });
visited[x][y] = idx;
popul += map[x][y];
cnt++;
}
}
}
if (cnt > 0) {
movePopul(idx, popul, cnt);
}
idx++;
}
}
return flag;
}
public static void movePopul(int idx, int popul, int cnt) {
int population = popul / cnt;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (visited[i][j] == idx)
map[i][j] = population;
}
}
}
public static boolean isRange(int x, int y) {
return x >= 0 && y >= 0 && x < N && y < N;
}
}