16234-인구이동 (오답)

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값을 가진 값을 찾아서 묶어주기엔 ...