[백준] 16234번 : 인구 이동 - 자바[Java]

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

16234번: 인구 이동

풀이

N*N 크기의 배열을 탐색하여 국경선이 열려 연결되는 국가를 찾아내고, 그 국가의 인구 수를 변경해야 한다.

먼저 2중 for문으로 N*N 크기의 배열을 탐색하고, 각 위치마다 BFS를 통해 연결되는 위치들을 찾아내서 인구 수의 총합을 찾아내고 변경해야 한다.

 

main() 함수의 로직

1. N, L, R을 입력받고 N*N 크기의 배열을 할당하고 값을 입력받는다.

2. while문을 사용해 인구 이동이 며칠 동안 발생하는지 구한다. 인구 이동이 발생하는 일수는 cnt에 저장한다.

3. while문 내에서 2중 for문을 사용하여 배열의 모든 위치에서 BFS를 수행한다.

4. bfs() 함수는 인구 이동이 일어났는지 여부를 반환한다. 하루동안 인구 이동이 일어나지 않았다면 isChange는 false가 되므로 while문을 종료한다.

5. cnt를 출력한다.

 

boolean bfs(boolean[][] visited, int i, int j)

bfs() 함수는 인구 이동이 일어났으면 true, 일어나지 않았으면 false를 반환한다.

1. 현재 시작 위치가 이미 이전에 탐색한 위치라면 false를 반환하고 종료한다.

2. 두 개의 Queue를 선언한다. q는 BFS에 사용할 큐이고, positions는 연결되어있는 칸의 위치를 저장한다.

3. sum은 연결되어있는 국가의 인구 수 총합을 저장한다.

4. q, positions에 시작 위치를 추가하고 시작점의 visited도 true로 변경한다.

5. BFS를 수행한다. 현재 위치에 대해 4방향을 탐색하고 조건을 만족하면 q, positions에 추가하고 visited와 sum 값을 업데이트한다.

6. sum / positions.size()로 새로운 인구 수를 구한다. newValue가 sum 값과 같으면 인구 이동이 일어나지 않았으므로 false를 리턴한다. 같지 않으면 positions에 저장된 모든 위치에 newValue 값으로 변경하고 true를 리턴한다.

 

코드

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

public class Main {
	
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	static int[][] arr;
	static int n, l, r;
	
    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());
    		}
    	}
    	
    	int cnt = 0;
    	
    	while(true) {
    		boolean isChange = false;
    		
    		boolean[][] visited = new boolean[n][n];
    		for (int i = 0; i < n; i++) {
        		for (int j = 0; j < n; j++) {
        			if (bfs(visited, i, j)) {
        				isChange = true;
        			}
        		}
        	}
    		
    		if (!isChange) break;
    		cnt++;
    	}
    	
    	System.out.println(cnt);
    	
    }
    
    public static boolean bfs(boolean[][] visited, int i, int j) {
    	if (visited[i][j]) {
    		return false;
    	}
    	
    	Queue<int[]> q = new LinkedList<>();
    	Queue<int[]> positions = new LinkedList<>();
    	int sum = arr[i][j];
    	
    	q.add(new int[]{i,j});
    	positions.add(new int[]{i,j});
    	visited[i][j] = true;
    	
    	while(!q.isEmpty()) {
    		int[] cur = q.poll();
    		int x = cur[0];
    		int y = cur[1];
    		
    		for (int dir = 0; dir < 4; dir++) {
    			int nx = x + dx[dir];
    			int ny = y + dy[dir];
    			
    			if (!checkIndex(nx, ny, n) || visited[nx][ny]) continue;
    			
    			int diff = Math.abs(arr[x][y] - arr[nx][ny]);
    			if (diff >= l && diff <= r) {
    				q.add(new int[]{nx, ny});
    				positions.add(new int[]{nx, ny});
    				visited[nx][ny] = true;
    				sum += arr[nx][ny];
    			}
    		}	
    	}
    	
    	int newValue = sum / positions.size();
    	
    	if (newValue == sum) {
    		return false;
    	}
    	
    	for (int[] pos: positions) {
    		arr[pos[0]][pos[1]] = newValue;
    	}
    	return true;
    }
    
    public static boolean checkIndex(int x, int y, int n) {
    	return x >= 0 && x < n && y >= 0 && y < n;
    }
}

 

visited 배열은 while문 내에서 2중 for문을 시작하기 전에 생성된다. 보통 BFS 문제를 풀 때는 BFS를 시작하기 전에 visited 배열을 생성하지만, 이 문제에서는 불필요한 탐색을 줄이기 위해 모든 배열 위치를 탐색하기 전에 visited 배열을 생성하였다.