[백준] 16234 인구이동

www.acmicpc.net/problem/16234

16234번: 인구 이동

2020-12-16

---

# 2019-08-24 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    public static int N, L, R, arr[][], map[][];
    public static boolean vtd[][];
    public static Queue<int[]> q, m;
    public static int dx[] = {-1, 0, 1, 0};
    public static int dy[] = {0, -1, 0, 1};
    
    public static boolean solve(int input) {
        boolean check = false;
        while(!q.isEmpty()) {
            int tmp[] = q.poll();
            int x = tmp[0];
            int y = tmp[1];
            for(int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                if(Math.abs(arr[nx][ny] - arr[x][y]) >= L && 
                        Math.abs(arr[nx][ny] - arr[x][y]) <= R
                        && !vtd[nx][ny]) {
                    check = true;
                    q.add(new int[] {nx, ny});
                    map[nx][ny] = input;
                    vtd[nx][ny] = true;
                }
            }
        }
        
        return check;
    }
    
    public static void move(int color) {
        int count = 1;
        int pop = 0;
        while(!m.isEmpty()) {
            int tmp[] = m.poll();
            int x = tmp[0];
            int y = tmp[1];
            pop += arr[x][y];
            for(int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                if(!vtd[nx][ny] && map[nx][ny] == map[x][y]) {
                    vtd[nx][ny] = true;
                    m.add(new int[] {nx, ny});
                    count++;
                }
            }
        }
        int res = pop / count;
        for(int i = 0; i < N; i++) 
            for(int j = 0; j < N; j++)
                if(map[i][j] == color) arr[i][j] = res;
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.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(bf.readLine());
            for(int j = 0; j < N; j++)
                arr[i][j] = Integer.parseInt(st.nextToken());
        }
        int count = 0;
        while(true) {
            int idx = 1;
            q = new LinkedList<int[]>();
            boolean check = false;
            vtd = new boolean[N][N];
            map = new int[N][N];
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < N; j++) {
                    if(!vtd[i][j]) {
                        q.add(new int[]{i, j});
                        vtd[i][j] = true;
                        map[i][j] = idx;
                        if(solve(idx)) {
                            check = true;
                        }
                        idx++;
                    }
                }
            }
            if(!check) break;
            else count++;
            m = new LinkedList<int[]>();
            vtd = new boolean[N][N];
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < N; j++) {
                    if(!vtd[i][j]) {
                        vtd[i][j] = true;
                        m.add(new int[] { i, j });
                        move(map[i][j]);
                    }
                }
            }
        }
        System.out.println(count);
    }
}
 

 

# 2020-12-16 풀이

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
    public static int N, L, R, people, count, answer, arr[][];
    public static boolean flag, vtd[][];
    public static Queue<int[]> q, f;
    public static int dx[] = {-1, 0, 1, 0};
    public static int dy[] = {0, -1, 0, 1};
    
    public static void solve() {
        while(!q.isEmpty()) {
            int tmp[] = q.poll();
            int x = tmp[0];
            int y = tmp[1];
            
            for(int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                else if(!vtd[nx][ny] && (Math.abs(arr[nx][ny] - arr[x][y]) >= L) && 
                        Math.abs(arr[nx][ny] - arr[x][y]) <= R) {
                    q.add(new int[] {nx, ny});
                    f.add(new int[] {nx, ny});
                    people += arr[nx][ny];
                    vtd[nx][ny] = true;
                    count++;
                    flag = true;
                }
            }
        }
        if(flag) {
            open();
        }
    }
    
    public static void open() {
        int num = people/count;
        while(!f.isEmpty()) {
            int tmp[] = f.poll();
            int x = tmp[0];
            int y = tmp[1];
            arr[x][y] = num;
        }
    }
    
    public static void init() {
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++) 
                vtd[i][j] = false;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        L = sc.nextInt();
        R = sc.nextInt();
        
        arr = new int[N][N];
        vtd = new boolean[N][N];
        q = new LinkedList<int[]>();
        f = new LinkedList<int[]>();
        answer = 0;
        
        for(int i = 0; i < N; i++) 
            for(int j = 0; j < N; j++) 
                arr[i][j] = sc.nextInt();
        
        loop:while(true) {
            flag = false;
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < N; j++) {
                    if(!vtd[i][j]) {
                        people = 0;
                        count = 1;
                        vtd[i][j] = true;
                        q.add(new int[] {i, j});
                        f.add(new int[] {i, j});
                        people += arr[i][j];
                        solve();
                        f.clear();
                    }
                }
            }
            if(flag) answer++;
            else break loop;
            init();
        }
        System.out.println(answer);
    }
}

 

 

#문제풀이

1. N x N 땅을 돌면서 국경선을 열고 연합을 맺을 수 있는 나라들을 체크했다. 이 때 연합을 맺을 수 있는 나라를 f라는 또다른 queue에 따로 넣어줬었다. 

 

2. 글로벌로 연합 맺을 국가의 갯수와 인구수를 따로 저장을 했고, 연합을 맺은 국가가 있는 경우 땅의 인구수를 업데이트 해주었다.

 

 

# 비교

작년 8월에도 풀었었던 문제이다. 오늘 푼 방식이 완벽하게 효율적이라고는 말하지 못하겠지만, 적어도 작년에 왜 저렇게 풀었던 방식이 비효율적이라는 것은 알았다. 굳이 필요하지 않은 부분을 넣어서 시간이 몇 배는 많이 들게 하는 코드였다. 다시 풀어보길 잘했다라는 생각이 든다.