白駿16234号:人口移転






問題の説明

  • https://www.acmicpc.net/problem/16234
  • に隣接する2カ国の人口差がL以上R以下であれば、国境は開放される.
  • の開放的な境界では、移動可能な国間が連合体となり、連合体ごとに分かち合う人口総数の平均値となる.
  • AおよびBの境界は開放的であり、BおよびCの境界が開放的である場合、A−B−Cは同じ同盟である.
  • 方法

  • の2次元配列において個々のナビゲーションが必要であり、一定の条件下で隣接するブロック(結合)を形成しなければならないため、BFSが使用される.
  • pseudocode

    Main(){
    	while(flag){
        	v = new boolean[N][N]; // day가 바뀔때마다 방문을 초기화해야 합니다.
        	for(모든 행){
            	for(모든 열){
                	if(해당 국가를 아직 방문하지 않았다면){
                    	if(BFS){ // BFS는 Union이 형성되었는지 확인하는 코드입니다.
    	                    // 현재의 day에 Union이 실행되지 않을 때까지 while문이 진행됩니다.
                            // 하지만 !BFS면 flag=false는 올바르지 못한 코드입니다.
    						// 예를들어 (0,0)국가는 아무런 Union이 없고, (0,1),(1,0),(1,1)이 Union인 경우 문제가 발생합니다.                        
                        	flag = true // 하나라도 Union이 일어났다면 while문을 끝내지 않습니다.
    
                        }
                    }
                }
            }
        }
    }
    BFS(){
    	while(q가 빌 때 까지){
        	temp = q.poll();
            temp를 Union에 넣습니다.
            for(4방탐색을 진행하면서){
            	if(해당 방향으로 국가가 존재하며(board를 벗어나지 않으며),그 국가를 아직 방문하지 않았고,
                temp국가와 인접국가의 인구 차이가 L이상 R이하면){
                	q에 해당 국가를 넣습니다.
                    해당 국가를 방문처리 합니다.
                }
            }
        }
        if(해당 국가와 연합된 국가가 하나도 없다면){
        	return false;
        }else{ // 해당 국가와 연합이 형성된 국가들이 있다면
        	연합은 인구를 나눠가집니다.
            return true;
        }
    }

    正解

    import java.util.*;
    
    public class Main {
    	static int N, L, R;
    	static int[] dx = { 0, 1, -1, 0 };
    	static int[] dy = { 1, 0, 0, -1 };
    	static int[][] board;
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		N = sc.nextInt();
    		L = sc.nextInt();
    		R = sc.nextInt();
    		board = new int[N][N];
    		for (int i = 0; i < N; i++) {
    			for (int j = 0; j < N; j++) {
    				board[i][j] = sc.nextInt();
    			}
    		}
    		int day = 0;
    		boolean flag = true;
    		while (flag) {
    			flag = false;
    			day++;
    			boolean[][] v = new boolean[N][N];
    			for (int i = 0; i < N; i++) {
    				for (int j = 0; j < N; j++) {
    					if (!v[i][j]) {
    						int[] temp = { i, j };
    						if (BFS(temp, v)) { // 해당 국가에서 국경이 개방되는 국가가 존재한다면 한번 더 while이 실행될 수 있습니다.
    							flag = true;
    						}
    					}
    				}
    			}
    		}
    		System.out.println(day - 1);
    	}
    
    	public static boolean BFS(int[] start, boolean[][] v) {
    		Queue<int[]> q = new LinkedList<int[]>();
    		List<int[]> Union = new ArrayList<int[]>();
    		q.add(start);
    		v[start[0]][start[1]] = true;
    		while (!q.isEmpty()) {
    			int[] temp = q.poll();
    			Union.add(temp);
    			for (int d = 0; d < 4; d++) {
    				int nx = temp[0] + dx[d];
    				int ny = temp[1] + dy[d];
    				if (0 <= nx && nx < N && 0 <= ny && ny < N && !v[nx][ny]
    						&& L <= Math.abs(board[temp[0]][temp[1]] - board[nx][ny])
    						&& Math.abs(board[temp[0]][temp[1]] - board[nx][ny]) <= R) {
    					v[nx][ny] = true;
    					int[] temp2 = { nx, ny };
    					q.add(temp2);
    				}
    			}
    		}
    		int cnt = Union.size();
    		int Sum = 0;
    		if (cnt == 1) { // BFS를 시작한 국가만 Union에 포함된다는 건 곧 아무런 이동도 없다는 의미입니다.
    			return false;
    		} else {
    			for (int i = 0; i < cnt; i++) {
    				int[] pos = Union.get(i);
    				Sum += board[pos[0]][pos[1]];
    			}
    			for (int i = 0; i < cnt; i++) {
    				int[] pos = Union.get(i);
    				board[pos[0]][pos[1]] = Sum / cnt;
    			}
    			return true;
    		}
    	}
    
    }

    その他


    これは
  • 20日前に解決できなかった問題で、今日は私がよくやったと思って、もっと成長しました.