백준 16234번: 인구 이동

문제 설명

• https://www.acmicpc.net/problem/16234
• 인접한 두 국가의 인구 차이가 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일 전에는 못풀었던 문제인데 오늘은 깔끔히 풀어서 한층 더 성장한 기분입니다.