백준16234 : 인구 이동

백준16234 : 인구 이동

문제

2차원 배열에 국가별 인구 수가 주어져있을 때 인접한 국가의 인구수가 주어진 범위 내에 있으면 국경을 열어 인구이동을 하여 1/N인구로 만드는 작업을 반복할 때, 인구이동이 몇 번 일어나는 지 알아내는 문제

https://www.acmicpc.net/problem/16234

접근방법

• BFS를 이용해 인접한 영역을 확인하고 인구이동을 한다.

• 인구이동을 한 국가는 booelan moved[][] 를 이용해 표시한다.

• 한 번 전체 국가가 인구이동을 한 뒤에는 이동 수를 증가시키고 moved[][]를 초기화 해준다.

1. BFS를 이용해 인접한 영역 확인하기

• 2개의 boolean 2차원 배열을 사용해주었다.

  1) BFS 체크용 boolean 배열 check[][] 시간이 초과되지 않도록 이미 방문한 배열 체크

  2) 인구이동한 국가 확인용 boolean 배열 moved[][]

• 인접한 배열을 큐에 넣을지 결정하기 위해서는 다음의 네가지를 확인해주어야 한다.

  1) 배열의 범위를 벗어났는가

  • 이 경우는 애초에 배열을 2칸씩 크게 만들어서, 해당 원소의 값이 0인지 여부만 확인해주면 된다.

  2) 아직 인구이동이 되지 않은 지역인가

  • moved 배열 확인

  3) BFS가 이미 방문한 원소인가

  • check 배열 확인

  4) 인구차이가 범위 내에 있는가

• 위 네가지를 확인한 뒤에 큐에 넣어준다.

인구이동이 일어난 국가들의 인구 수를 변경해주기 위해, 큐에서 빼낸 좌표들은 다시 새로운 큐(queue_tmp)에 넣어준다.

• 해당 큐를 이용하여 인구 수를 설정해주고, moved를 함께 체크한다.

• 인접값을 확인하기 전부터 미리 하나는 큐에 들어가므로, 큐의 개수가 1개 초과일 경우가 인구이동이 일어난 경우이다.

소스코드

import java.util.*;
import java.io.*;
​
public class Main{
​
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
​
    static int N;
    static int minGap;
    static int maxGap;
    static int[][] map;
    static boolean[][] moved;
    static boolean isQuit;
​
    static class Pos{
        int x; int y;
        public Pos(int x, int y) {this.x= x; this.y = y;}
    }
​
    static void BFS(int x, int y){
        boolean check[][] = new boolean[N+2][N+2];
        Queue<Pos> queue = new LinkedList();
        Queue<Pos> queue_tmp = new LinkedList();
        queue.offer(new Pos(x, y));
​
        int sum = 0;
        while(!queue.isEmpty()) {
            Pos cur_pos = queue.poll();
            check[cur_pos.x][cur_pos.y] = true;
            sum += map[cur_pos.x][cur_pos.y];
            queue_tmp.offer(new Pos(cur_pos.x, cur_pos.y));
​
            for (int i = 0; i < 4; i++) {
                Pos next_pos = new Pos(cur_pos.x + dx[i], cur_pos.y + dy[i]);
                int gap = Math.abs(map[cur_pos.x][cur_pos.y] - map[next_pos.x][next_pos.y]);
                if( map[next_pos.x][next_pos.y] != 0        // 경계가 아니면서
                        && !moved[next_pos.x][next_pos.y]   // 아직 인구이동이 되지 않은 지역이면서
                        && !check[next_pos.x][next_pos.y]   // <<BFS방문체크>>
                        && gap >= minGap && gap <= maxGap){ // 인구 차이가 범위 내인 경우
                    queue.offer(next_pos);                  // 큐에 넣어준다.
                    check[next_pos.x][next_pos.y] = true;
                }
            }
        }
​
        // 인구이동이 일어난 경우
        if(queue_tmp.size() != 1){
            isQuit = false;
            int value = sum / queue_tmp.size();
            while(!queue_tmp.isEmpty()){
                Pos pos = queue_tmp.poll();
                map[pos.x][pos.y] = value;
                moved[pos.x][pos.y] = true;
            }
        }
​
    }
​
​
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] input = in.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        minGap = Integer.parseInt(input[1]);
        maxGap = Integer.parseInt(input[2]);
​
        map = new int[N+2][N+2];
        moved = new boolean[N+2][N+2];
        for(int i=1; i<=N; i++){
            String line[] = in.readLine().split(" ");
            for(int j=1; j<=N; j++)
                map[i][j] = Integer.parseInt(line[j-1]);
        }
​
        int result = 0;
        while(true){
            isQuit = true;
            for(int i=1; i<=N ;i++)
                for (int j = 1; j <= N; j++)
                    if (!moved[i][j])
                        BFS(i, j);
​
            if(!isQuit){
                ++result;
                // 인구이동여부 초기화
                for(int i=1; i<=N; i++)
                    for(int j=1; j<=N; j++)
                        moved[i][j] = false;
            } else{ // 인구이동 하나도 없을 시 종료
                break;
            }
        }
​
        System.out.println(result);
    }
}