인구이동

📍 문제 설명

 

💡 접근

1.먼저 국경선이 열려 인구이동이 발생하는 국가들에 대해 각각 그룹번호를 붙여주기 위한 배열을 하나 생성한다.

2.모든 지점에 대해서 탐색하는데 그룹번호가 붙여지지 않은 나라들에 대해서만 탐색한다.

3.해당 지점에서 상하좌우 확인하여 국경선이 열리는 나라라면 큐에 해당 좌표를 넣고 리스트에도 해당 좌표를 넣는다.

4.국경선이 열리는 것을 확인했으면 리스트에서 연합 국가들을 꺼내 인구를 분배한다.

5.연합번호가 n * n이 되면(인구이동을 할 수 없으면) 멈추고 아니면 1번으로 돌아가서 다시 수행한다.

 

 

👩‍💻 코드

import java.util.*;

class Position {
    private int x;
    private int y;

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

    public int getX() {
        return this.x;
    }

    public int getY() {
        return this.y;
    }

    @Override
    public String toString() {
        return "Position{" +
                "x=" + x +
                ", y=" + y +
                '}';
    }
}

public class Main {
    // 땅의 크기(N), L, R 값을 입력받기
    public static int n, l, r;
    public static int totalCount = 0;

    // 전체 나라의 정보(N x N)를 입력받기
    public static int[][] graph = new int[n][n];
    public static int[][] unions = new int[n][n];

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

    // 특정 위치에서 출발하여 모든 연합을 체크한 뒤에 데이터 갱신
    public static void process(int x, int y, int index) {
        System.out.println(Arrays.deepToString(graph));
        System.out.println(Arrays.deepToString(unions));
        // (x, y)의 위치와 연결된 나라(연합) 정보를 담는 리스트
        ArrayList<Position> united = new ArrayList<>();
        united.add(new Position(x, y));
        // 너비 우선 탐색 (BFS)을 위한 큐 라이브러리 사용
        Queue<Position> q = new LinkedList<>();
        q.offer(new Position(x, y));
        unions[x][y] = index; // 현재 연합의 번호 할당
        int summary = graph[x][y]; // 현재 연합의 전체 인구 수
        int count = 1; // 현재 연합의 국가 수
        // 큐가 빌 때까지 반복(BFS)
        while (!q.isEmpty()) {
            System.out.println(q);
            Position pos = q.poll();
            x = pos.getX();
            y = pos.getY();
            // 현재 위치에서 4가지 방향을 확인하며
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                // 바로 옆에 있는 나라를 확인하여
                if (0 <= nx && nx < n && 0 <= ny && ny < n && unions[nx][ny] == -1) {
                    // 옆에 있는 나라와 인구 차이가 L명 이상, R명 이하라면
                    int gap = Math.abs(graph[nx][ny] - graph[x][y]);
                    if (l <= gap && gap <= r) {
                        q.offer(new Position(nx, ny));
                        // 연합에 추가하기
                        unions[nx][ny] = index;
                        summary += graph[nx][ny];
                        count += 1;
                        united.add(new Position(nx, ny));
                    }
                }
            }
        }
        // 연합 국가끼리 인구를 분배
        for (int i = 0; i < united.size(); i++) {
            x = united.get(i).getX();
            y = united.get(i).getY();
            graph[x][y] = summary / count;
        }
        System.out.println("summary : " + summary);
        System.out.println("count : " + count);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        l = sc.nextInt();
        r = sc.nextInt();
        graph = new int[n][n];
        unions = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                graph[i][j] = sc.nextInt();
            }
        }

        // 더 이상 인구 이동을 할 수 없을 때까지 반복
        while (true) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    unions[i][j] = -1;
                }
            }
            System.out.println("unions -1로 초기화!");
            int index = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (unions[i][j] == -1) { // 해당 나라가 아직 처리되지 않았다면
                        System.out.println(i + ", " + j + ", " + index + " 에서 process 함수 호출합니다.");
                        process(i, j, index);
                        index += 1;
                        System.out.println("index : " + index);
                        System.out.println();
                    }
                }
            }
            // 모든 인구 이동이 끝난 경우
            if (index == n * n) break;
            totalCount += 1;
        }

        // 인구 이동 횟수 출력
        System.out.println(totalCount);
    }
}