package com.exam;
import java.util.*;
public class B16234 {
static final int MAX_N = 10;
static int n,l,r, result;
static int[][] Board = new int[MAX_N][MAX_N];
static int[][] D = {{-1,0},{1,0},{0,-1},{0,1}};
static ArrayList<Node> union;
static Queue<Node> queue;
static boolean[][] visited;
static class Node{
int col,row=0;
Node(int row, int col){
this.row=row;
this.col=col;
}
}
public static int move(){
while(true) {
// 해당 노드에 방문했는지 확인하기위해
visited = new boolean[n][n];
// 인구변경이 일어났는지 확인하기위해
boolean isMove = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j]) {
int avg = bfs(i, j);
if (avg == -1) {
continue;
}
if (union.size() > 1) {
setAvg(avg);
isMove = true;
}
}
}
}if(!isMove) return result;
//인구변경이 일어났으면 ++
result ++;
}
}
public static void setAvg(int avg){
for(Node node : union){
//해당 연합에 해당하는 국가들의 인구 평균 구하기
Board[node.row][node.col] = avg;
}
}
public static int bfs(int sRow, int sCol){
queue = new LinkedList<>();
visited[sRow][sCol] = true;
queue.add(new Node(sRow,sCol));
// 연합에 node정보 담기
union = new ArrayList<>();
union.add(new Node(sRow,sCol));
int sum = Board[sRow][sCol];
while(!queue.isEmpty()){
Node curr = queue.remove();
for(int i=0; i<4; i++){
// 해당 노드의 상하좌우 탐색
int nr = curr.row+D[i][0];
int nc = curr.col+D[i][1];
// 만약 범위 밖이거나 이미 방문했으면 건너뛰기
if(nr<0 || nr>n-1 || nc<0 || nc>n-1)continue;
if(visited[nr][nc])continue;
int minus = Math.abs(Board[curr.row][curr.col]-Board[nr][nc]);
// 노드와 탐색노드 차가 입력한 범위내면
if(minus>=l && minus<=r){
//방문등록 후 큐와 연합에 정보 담기
visited[nr][nc] = true;
queue.add(new Node(nr,nc));
union.add(new Node(nr,nc));
sum += Board[nr][nc];
}
}
}
if(union.size()>1) {
return sum / union.size();
}else{
return -1;
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
l = sc.nextInt();
r = sc.nextInt();
Board = new int[n][n];
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
Board[i][j] = sc.nextInt();
}
}
System.out.println(move());
}
}
'연습문제 > JAVA' 카테고리의 다른 글
2178-미로탐색 (0) | 2022.08.07 |
---|---|
1620-DFS와 BFS (0) | 2022.08.06 |
16234-인구이동 (오답) (0) | 2022.08.04 |
Java- Example6번 ( p506~507 ) (0) | 2021.08.13 |
Java- FileExample5번 (p490 ~ 491) (0) | 2021.08.13 |