16234-인구이동 문제
package com.exam;
import java.util.*;
public class BAEK16234 {
static int[][] intArr;
static int n, firstNum , secondNum;
static int result;
static Map<String,Map<String, Integer>> numMap;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
firstNum = sc.nextInt();
secondNum = sc.nextInt();
intArr = new int[n][n];
for (int y = 0; y < n; y++) {
for (int x = 0; x < n; x++) {
// intArr[][]은 N x N 크기의 땅을 나타낸다
// 한칸에 하나의 나라가 있다
intArr[y][x] = sc.nextInt();
}
}
System.out.println(move());
}
public static int move(){
// numMap은
//중첩 Map을 사용하여 연관된 노드, Map<key,value> 를 저장한다
//key는 intArr의 좌표를 String값으로 저장
numMap = new HashMap<>();
do {
numMap.clear();
// i=y & j=x
for(int i=0; i<n; i++){
for(int j=0; j<n-1; j++){
// x축으로 바로 옆 나라와 인구수를 비교
// y축으로 바로 아래 나라와 인구 수 비교를 동시에 해준다
int colMinus = Math.abs(intArr[i][j]-intArr[i][j+1]);
int rowMinus = Math.abs(intArr[j][i]-intArr[j+1][i]);
// 여기는 x축으로 인구수를 비교
if(colMinus>=firstNum && colMinus<=secondNum) {
boolean match = false;
for (String key : numMap.keySet()) {
//해당 키값이 numMap에 존재하면 연관된 노드라는 뜻
if (numMap.get(key).get(String.valueOf(i) + j) != null) {
numMap.get(key).put(String.valueOf(i) + (j + 1), intArr[i][j + 1]);
match = true;
} else if (numMap.get(key).get(String.valueOf(i) + (j + 1)) != null) {
numMap.get(key).put(String.valueOf(i) + j, intArr[i][j]);
match = true;
}
}
// 연관된 노드가 없으면 자기자신의 키값으로
// 이중Map을 생성한다
if (!match) {
Map<String, Integer> valueMap = new HashMap<>();
numMap.put(String.valueOf(i) + j, valueMap);
valueMap.put(String.valueOf(i) + j, intArr[i][j]);
valueMap.put(String.valueOf(i) + (j+1), intArr[i][j+1]);
}
}
// 여기는 y축으로 인구수를 비교
if(rowMinus>=firstNum && rowMinus<=secondNum) {
boolean match = false;
for (String key : numMap.keySet()) {
if (numMap.get(key).get(String.valueOf(j) + i) != null) {
numMap.get(key).put(String.valueOf(j + 1) + i, intArr[j + 1][i]);
match = true;
} else if (numMap.get(key).get(String.valueOf(j + 1) + i) != null) {
numMap.get(key).put(String.valueOf(j) + i, intArr[j][i]);
match = true;
}
}
if (!match) {
Map<String, Integer> valueMap = new HashMap<>();
numMap.put(String.valueOf(j) + i, valueMap);
valueMap.put(String.valueOf(j) + i, intArr[j][i]);
valueMap.put(String.valueOf(j + 1) + i, intArr[j + 1][i]);
}
}
}
}
setAvg();
if(!numMap.isEmpty()){
result++;
}
}
while(!numMap.isEmpty());
return result;
}
public static void setAvg(){
//여기서 numMap의 연관된 노드 리스트 끼리
// 평균을 구하여 set
for(String key : numMap.keySet()){
int sum = 0;
int count = 0;
int avg;
for(String subKey : numMap.get(key).keySet() ){
sum += numMap.get(key).get(subKey);
count++;
}
avg = sum/count;
for(String subKey : numMap.get(key).keySet() ){
int a = Character.getNumericValue(subKey.toCharArray()[0]);
int b = Character.getNumericValue(subKey.toCharArray()[1]);
intArr[a][b] = avg;
}
}
}
}
다음 배열을 넣으면 3번의 인구이동이 나온다
인구이동이 일어나는 나라를 numMap으로 나타냈다
(10={11=100, 33=10 ...} ) 여기서 10이 대표 연관노드 key값(좌표)이고 해당 노드와 연관된 모든 노드들이
뒤에 들어있다.
연관 노드정보가 들어있는 numMap과
인구이동 실행 후 각 나라의 인구수 intArr를 출력했다
3번째 실행중 오류
위 코드는 좌에서 우, 위에서 밑으로 탐색을 실행하는데
다음과 같이 for문에서
0,0부터 0,3까지 그리고 0,0부터 3,0 까지 탐색
1,0부터 1,3까지 그리고 0,1부터 3,1 까지 순서로 쭉 반복된다
2번을 수행하는 중 좌에서 우로만 탐색을 수행하니 왼쪽의 수(1,1)을 탐색못해서
두개의 묶음이 발생한다
그렇다고 탐색 후 마지막에 각 묶음에 같은 key값을 가진 값을 찾아서 묶어주기엔 ...
'연습문제 > JAVA' 카테고리의 다른 글
1620-DFS와 BFS (0) | 2022.08.06 |
---|---|
16234-인구이동 (0) | 2022.08.05 |
Java- Example6번 ( p506~507 ) (0) | 2021.08.13 |
Java- FileExample5번 (p490 ~ 491) (0) | 2021.08.13 |
Java- FileExample4번 (p487) (0) | 2021.08.13 |