백준 - 인구 이동(16234) - Java

1. 문제

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

2. 풀이

참고 풀이
https://github.com/ndb796/python-for-coding-test/blob/master/13/7.java

각 나라의 위치에서 BFS를 수행하여, 연결되어 있는 모든 나라들(연합)을 찾는다.

2-1. ✨핵심 Point

1. while(true)로 BFS수행

2. 한번의 BFS때마다 좌표들을 저장해서 해당 좌표들의 각 인구수를 갱신한다.

3. 코드

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

public class Main{
    
    static int N;
    static int L;
    static int R;
    static int map[][];
    static int unions[][];
    static int moveX[] = {1, -1, 0, 0};
    static int moveY[] = {0, 0, 1, -1};
    
    public static class Node{
        int x;
        int y;
        
        public Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    
    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());
        
        map = new int[N][N];
        unions = new int[N][N];
        
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < N; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        int totalCount = 0;
        while(true){
            for(int i = 0; i < N; i++){
                Arrays.fill(unions[i], -1);
            }
            
            int index = 0;
            for(int i = 0; i < N; i++){
                for(int j = 0; j < N; j++){
                    if(unions[i][j] == -1){
                        bfs(i, j, index);
                        index += 1;
                    }
                }
            }
            
            if(index == N * N) // 모든 도시의 방문이 끝나면
                break;
            totalCount += 1;
        }
        System.out.println(totalCount);
    }
    
    public static void bfs(int x, int y, int index){
        ArrayList<Node> unionList = new ArrayList<>();
        Queue<Node> q = new LinkedList<>();
        
        unions[x][y] = index;
        unionList.add(new Node(x, y));
        q.add(new Node(x, y));
        
        int count = 1;
        int sum = map[x][y];
        
        while(!q.isEmpty()){
            Node node = q.poll();
            
            for(int i = 0; i < 4; i++){
                int goX = node.x + moveX[i];
                int goY = node.y + moveY[i];
                
                if(goX < 0 || goY < 0 || goX >= N || goY >= N)
                    continue;
                
                if(unions[goX][goY] == -1){
                    int gap = Math.abs(map[node.x][node.y] - map[goX][goY]);
                    if(gap >= L && gap <= R){
                        unions[goX][goY] = index;
                        unionList.add(new Node(goX, goY));
                        q.add(new Node(goX, goY));
                        count += 1;
                        sum += map[goX][goY];    
                    }
                }
            }
        }
        for(Node node : unionList){
            map[node.x][node.y] = sum / count;
        }
    }
}