[백준][구현/BFS][Java] 16234. 인구이동 : 골드 4

문제 링크 : https://www.acmicpc.net/problem/16234

문제 풀이 시간 : 56분

 

문제를 요약해보자면, 하루 동안 다음 과정이 반복된다:

1. 인접한 나라의 인구 차이가 L ~ R이면 국경을 연다
2. 연결된 나라들을 하나의 연합으로 묶음.
3. 연합의 인구를 평균으로 갱신한다
4. 더 이상 이동이 없을 때까지 반복한다.

처음에는 아래와 같은 경우를 고려하지 못해서, 다 같은 연합으로 묶어 계산해서 틀렸다...

 

4%에서 틀린다면,, 이게 문제이니 참고하세용.. ~

 

암튼 처음 구현한거 틀려서 20분은 날려버림. 항상 문제 의도를 잘 파악하자. 테스트 케이스 잘 생각해보고 구현하기.

 

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

class Main{

    static int[][] arr;
    static boolean[][] opened;
    static int N, L, R;
    static int[] dx = {-1, 1, 0, 0};
    static int[] 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());

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

        arr = new int[N][N];


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

        boolean flag;
        int total = 0;
        while(true){
            opened = new boolean[N][N];
            flag = false;
            for(int i =0; i < N; i++){
                for(int j = 0; j <N; j++){
                    if(opened[i][j])
                        continue;

                    if(bfs(i, j))
                        flag = true;

                }
            }
            if(!flag) // 인구이동이 없었다는 뜻.
                break;

            total++; // 하루가 지나감.
        }
        System.out.print(total);
    }

    public static boolean bfs(int i, int j){
        Queue<Point> q = new LinkedList<>();
        Queue<Point> change = new LinkedList<>();

        q.add(new Point(i, j));
        change.add(new Point(i, j));

        int sum = arr[i][j];
        int count = 1;
        opened[i][j] = true;
        boolean flag = false;

        while (!q.isEmpty()) {
            Point cur = q.poll();
            for (int a = 0; a < 4; a++) {
                int next_i = cur.i + dx[a];
                int next_j = cur.j + dy[a];

                if (next_i < 0 || next_i >= N || next_j < 0 || next_j >= N)
                    continue;

                if(opened[next_i][next_j])
                    continue;

                int dif = Math.abs(arr[cur.i][cur.j] - arr[next_i][next_j]);

                if(dif >= L && dif <= R){
                    opened[next_i][next_j] = true;
                    flag = true;
                    q.add(new Point(next_i, next_j));
                    change.add(new Point(next_i, next_j));
                    sum += arr[next_i][next_j];
                    count ++;
                }

            }
        }

        sum /= count;
        while(!change.isEmpty()){
            Point cur = change.poll();
            arr[cur.i][cur.j] = sum;
        }

        return flag;
    }

    public static class Point{
        int i, j;
        public Point(int i, int j){
            this.i = i;
            this.j = j;
        }
    }
}