[백준] 16234번: 인구 이동 (Java)

1. 문제설명

NxN 크기의 땅이 있고, 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 인구 이동은 하루동안 아래와 같이 진행되고, 더이상 인구 이동이 없을 때까지 지속된다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 문제이다.

• 시간 제한: 2초
• 메모리 제한: 512MB

 

2. 접근 방식

• while문으로 인구 이동이 일어났는지 확인하고, 더 이상 인구 이동이 발생하지 않을 때까지 반복한다.
• 매 반복 시작 시, 방문 여부 확인하는 배열(`visited`)를 초기화하고,
  모든 나라에 대해 방문하지 않은 경우 BFS 탐색한다.
• 인접한 나라와의 인구 차이가 조건에 부합하면
  • 큐에 해당 위치를 넣고 방문 처리한다.
  • 연합 인구 계산을 위해 해당 위치를 별도의 큐에 저장한다.
  • “연합의 인구수”에 해당 나라의 인구수를 더하고, “연합을 이루고 있는 칸의 개수”를 1 증가시킨다.
• 더 이상 조건에 부합하는 인접한 나라가 없다면(큐가 빌 경우), BFS 탐색을 종료한다.
  • 연합을 이루는 나라의 인구수를 `(연합의 인구수)/(연합을 이루고 있는 칸의 개수)`로 설정한다.
• 인구 이동이 발생했을 경우에만 `day`를 증가시킨다.

 

3. 다른 풀이

https://moonsbeen.tistory.com/259

[백준]16234: 인구 이동 - JAVA

내가 푼 방식이 적절한 방식인지 확인하고 싶어서 다른 풀이를 찾아보았다.

전반적으로 비슷했는데, 조금 더 효율적인 방법을 찾았다.

나는 연합인 나라를 큐에 저장하고 연합인 나라의 개수를 BFS에서 증가시키는 방법을 사용했는데, 
참고한 풀이는 `ArrayList`로 연합인 나라의 위치를 저장하고, `size()`를 사용해서 평균값을 구했다.

나처럼 굳이 `count` 변수를 생성할 필요가 없는 방법이었다. 

작더라도 이런 효율적으로 코드를 작성할 수 있도록 노력해야겠다.

 

 

4. 최종 코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, L, R;
    static int[][] country; // 각 나라의 인구 정보 저장
    static boolean[][] visited; // 방문 여부 확인

    // 상하좌우
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static boolean bfs(int x, int y) {
        Queue<int[]> q = new ArrayDeque<>(); // BFS에 사용할 큐
        q.add(new int[]{x, y}); // 시작 위치 큐에 추가
        Queue<int[]> union = new ArrayDeque<>(); // 연합인 나라의 위치를 저장할 큐
        union.add(new int[]{x, y});
        visited[x][y] = true; // 시작 위치 방문 처리

        int population = country[x][y]; // 연합의 인구수
        int count = 1; // 연합을 이루고 있는 칸의 수

        while(!q.isEmpty()){
            int[] cur = q.poll(); // 큐에서 현재 위치 꺼냄
            for(int i=0; i<4; i++) { // 상하좌우로 인접한 칸 탐색
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];
                // 땅의 범위 내에 있고, 아직 방문하지 않은 칸일 경우
                if(nx>=0 && nx<N && ny>=0 && ny<N && !visited[nx][ny]) {
                    // 인구 차이 계산
                    int absDif = Math.abs(country[cur[0]][cur[1]] - country[nx][ny]);
                    if(absDif>=L && absDif<=R) { // 인구 차이가 L이상 R이하일 경우
                        q.add(new int[]{nx, ny}); // 다음 탐색 위한 큐에 추가
                        visited[nx][ny] = true; // 방문 처리
                        union.add(new int[]{nx, ny}); // 연합 큐에 추가
                        population += country[nx][ny]; // 연합 총 인구수 갱신
                        count++; // 연합 이루는 칸의 수 증가
                    }
                }
            }
        }

        if(count > 1) { // 연합을 이루는 나라가 있다면
            int newPopulation = population/count; // 새로운 인구수 계산
            while(!union.isEmpty()) {
                // 연합에 속한 칸에 인구수 갱신
                int[] qq = union.poll();
                country[qq[0]][qq[1]] = newPopulation;
            }
            return true; // 인구 이동 일어남 (반환)
        }
        return false; // 인구 이동 일어나지 않음 (반환)
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        country = new int[N][N];
        for(int i=0; i<N; i++) { // 각 나라의 인구 정보 저장
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++) {
                country[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int day = 0; // 인구 이동이 발생한 날 수
        boolean check = true; // 인구 이동이 일어났는지 확인
        while(check) { // 인구 이동이 더이상 없으면 종료
            check = false; // 인구 이동 확인 초기화
            visited = new boolean[N][N]; // 방문 여부 배열 초기화
            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {
                    if(!visited[i][j]) { // 방문하지 않은 나라일 경우
                        // BFS를 수행하고, 인구 이동이 발생하면 check를 true로 설정
                        if(bfs(i, j)) check = true;
                    }
                }
            }

            if(check) day++; // 인구 이동이 발생했으면 day를 증가
        }

        System.out.println(day);
    }
}

 

4. 느낀점 or 기억할정보

절대값을 구할 때 `Math.abs()`를 사용하면 된다.

BFS 탐색을 설계하는 것은 이제 익숙해진 것 같다. 하지만 BFS를 호출하는 것을 어떤 식으로 반복할지 생각하는 데 오래걸렸다.

이 문제는 인구 이동이 더 이상 발생해지 않을 때까지 반복을 통해 BFS를 호출해야 했다. bfs 메서드에서 인구 이동이 발생했는지 안했는지 반환하고, 그 반환값을 이용해 while문을 계속 실행할지 종료할지 설정하는 방법을 사용했다.