BOJ) 인구 이동

인구 이동

16234번: 인구 이동

풀이

 

인접해있는 땅과 인구의 차이가 주어진 L과 R 사이에 존재하면 평균을 내면서, L과 R 사이에 존재하지 않을 때 까지 묶어주는 문제다.

 

처음 제출하자마자 맞았지만, 효율성이 조금 떨어진다고 생각해서 코드를 수정했다.

얼마 전 포스팅했던 성곽 문제랑 푸는 방법이 비슷하다.

grouping을 해주고 각 group의 평균 값을 HashMap에 저장한다. 전체 grouping이 끝나면, 각 gourp마다 평균 값을 넣어주면서 조건에 부합하지 않을 때 까지 while으로 반복했다.

 

코드가 길어서 복잡해보이지만, main은 입력값 저장을 해주는 것이 전부이고, solution이 위에서 말한 로직을 실행한다.

맵을 탐색하면서 group ==0인 경우 (아직 그룹이 정해지지 않은 경우)에 grouping을 해주면서 동시에 nations (나라의 수를) 세주었다.

또한, int형 변수 populations에 인구 수를 저장하면서, 마지막에 HashMap에 넣을 때, populations/nations 로 평균 값을 저장했다.

 

코드 1

사진처럼, 메모리와 시간이 좋지 못한 코드다.

더 좋게 바꿀 수 없을지 고민하다가, HashMap에 저장하고 호출하지말고 group의 index를 가진 배열을 생성해서 저장하고 호출하게 바꿨다.

group의 수는 grouping을 하기 전까지 알 수 없지만, 모두 인접한 곳과 인구이동을 할 수 없는 경우 각자 하나씩 group이 되기 때문에 최대 N*N개의 그룹이 생성되는 것을 유추했다.

 

group의 평균인구를 담을 newPopulations 배열을 생성하고, HashMap에 저장했던 위치에 배열에 저장하도록 했다.

 

코드 2

 

눈에 띄게 확 좋아졌다고는 할 수 없지만, 조금 더 효율적인 코드라고 할 수 있다.

메모리를 적게 쓰고 빠르게 푼 사람들은 어떻게 풀었는지 봤는데, find-union으로 푼 사람이 대부분이었다.grouping하는 자체가 find-union으로 대체 가능하기 때문에, 다음에 풀 기회가 생기면 find-union으로 풀어봐야겠다. 

 

 

 

 

 

 

코드 1

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    final static int[] dx = {1,-1,0,0}, dy = {0,0,1,-1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());

        int[][] map = new int[N][N];
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        solution(N,L,R,map);
        br.close();
    }

    private static void solution(int N, int L, int R, int[][] map) {
        int answer =0;
        boolean isChange = true;

        while(isChange) {
            isChange = false;
            int[][] group = new int[N][N];
            int groupIdx =0;
            LinkedList<Pos_16234> moveList = new LinkedList<>();
            HashMap<Integer,Integer> populationMap = new HashMap<>();

            for(int y=0; y<N; y++) {
                for(int x=0; x<N; x++) {
                    if(group[y][x] ==0) {
                        group[y][x] = ++groupIdx;
                        moveList.offer(new Pos_16234(x,y));
                        int nations =1;
                        int populations = map[y][x];

                        while(!moveList.isEmpty()) {
                            Pos_16234 pos = moveList.poll();

                            for(int i=0; i<4; i++) {
                                int nx = pos.x +dx[i];
                                int ny = pos.y +dy[i];
                                if(isInArea(nx,ny,N)) {
                                    if(group[ny][nx] ==0 && isUnited(map[pos.y][pos.x], map[ny][nx], L, R)) {
                                        isChange = true;
                                        group[ny][nx] = groupIdx;
                                        nations++;
                                        populations += map[ny][nx];
                                        moveList.offer(new Pos_16234(nx,ny));
                                    }
                                }
                            }
                        }
                        populationMap.put(groupIdx, populations/nations);
                    }
                }
            }
            if(isChange) {
                answer++;
            }

            for(int y=0; y<N; y++) {
                for(int x=0; x<N; x++) {
                    map[y][x] = populationMap.get(group[y][x]);
                }
            }
        }
        System.out.println(answer);
    }

    private static boolean isUnited(int val1, int val2, int L, int R) {
        return Math.abs(val1-val2) >= L && Math.abs(val1-val2) <=R;
    }

    private static boolean isInArea(int x, int y, int max) {
        return x>=0 && x<max && y>=0 && y<max;
    }
}

class Pos_16234 {
    int x;
    int y;

    public Pos_16234(int x, int y) {
        this.x= x;
        this.y = y;
    }
}

 

코드 2

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    final static int[] dx = {1,-1,0,0}, dy = {0,0,1,-1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());

        int[][] map = new int[N][N];
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        solution(N,L,R,map);
        br.close();
    }

    private static void solution(int N, int L, int R, int[][] map) {
        int answer =0;
        boolean isChange = true;

        while(isChange) {
            isChange = false;
            int[][] group = new int[N][N];
            int groupIdx =0;
            LinkedList<Pos_16234> moveList = new LinkedList<>();
            int[] newPopulations = new int[N*N+1];

            for(int y=0; y<N; y++) {
                for(int x=0; x<N; x++) {
                    if(group[y][x] ==0) {
                        group[y][x] = ++groupIdx;
                        moveList.offer(new Pos_16234(x,y));
                        int nations =1;
                        int populations = map[y][x];

                        while(!moveList.isEmpty()) {
                            Pos_16234 pos = moveList.poll();

                            for(int i=0; i<4; i++) {
                                int nx = pos.x +dx[i];
                                int ny = pos.y +dy[i];
                                if(isInArea(nx,ny,N)) {
                                    if(group[ny][nx] ==0 && isUnited(map[pos.y][pos.x], map[ny][nx], L, R)) {
                                        isChange = true;
                                        group[ny][nx] = groupIdx;
                                        nations++;
                                        populations += map[ny][nx];
                                        moveList.offer(new Pos_16234(nx,ny));
                                    }
                                }
                            }
                        }
                        newPopulations[groupIdx] = populations/nations;
                    }
                }
            }
            if(isChange) {
                answer++;
            }

            for(int y=0; y<N; y++) {
                for(int x=0; x<N; x++) {
                    map[y][x] = newPopulations[group[y][x]];
                }
            }
        }
        System.out.println(answer);
    }

    private static boolean isUnited(int val1, int val2, int L, int R) {
        return Math.abs(val1-val2) >= L && Math.abs(val1-val2) <=R;
    }

    private static boolean isInArea(int x, int y, int max) {
        return x>=0 && x<max && y>=0 && y<max;
    }
}

class Pos_16234 {
    int x;
    int y;

    public Pos_16234(int x, int y) {
        this.x= x;
        this.y = y;
    }
}