[백준] 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문을 계속 실행할지 종료할지 설정하는 방법을 사용했다.