[백준]JAVA - 16234번: 인구 이동

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

16234번: 인구 이동

풀이

인접해있는 땅과의 인구수 차이가 L과 R 사이이면 국경선이 열리고 연합 내의 동일한 인구수를 가진다.

 

위 문제는 bfs, dfs 아무거나 사용해도 무관하기 때문에 본인이 원하는 걸 사용하면 된다.

필자는 bfs를 이용해서 문제를 풀었다.

while (true) {
    visited = new boolean[N][N]; // 방문 유부
    isMove = false; // 변경 유무
			
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            if (!visited[i][j]) bfs(i, j);
        }
    }
			
    if (!isMove) break;
    ans++;
}

해당 문제는 더 이상 인접한 땅과의 인구수 차이가 L과 R 사이가 없을 때까지 돌려야 한다.

그렇기 때문에 무한 반복문 안에 인구수 변경 유무를 판단할 isMove 변수를 넣은 후에 더 이상 위 조건이 없을 때까지 bfs를 돌린다.

 

public static void bfs(int x, int y) {
    Queue<Position> q = new LinkedList<>();
    ArrayList<Position> arrList = new ArrayList<>(); // 인구수를 평균내기 위한 배열
		
    arrList.add(new Position(x, y)); // 시작 땅 추가
    q.add(new Position(x, y));
    visited[x][y] = true;
    int sum = map[x][y];
		
    while(!q.isEmpty()) {
        Position now = q.poll();
			
        for (int i=0; i<4; i++) {
            int nx = now.x + dx[i];
            int ny = now.y + dy[i];
				
            if (nx < 0 || nx > N-1 || ny < 0 || ny > N-1 || visited[nx][ny]) continue;
				
            int sumxy = Math.abs(map[nx][ny] - map[now.x][now.y]);
				
            // 조건에 해당하는 땅 (인구수 차이가 L과 R사이)
            if (L <= sumxy && sumxy <= R) {
                sum += map[nx][ny];
					
                arrList.add(new Position(nx, ny));
                q.add(new Position(nx, ny));
                visited[nx][ny] = true;
            }
        }
    }
		
    // 변경할 값이 존재할 경우
    if (arrList.size() > 1) {
        int num = sum / arrList.size();
        for (int i=0; i<arrList.size(); i++) {
            map[arrList.get(i).x][arrList.get(i).y] = num;
        }
			
        isMove = true;
    }
}

bfs는 아주 기본적인 구조에서 인구수를 변경해야 하는 조건에 들어맞는 땅을 넣을 arrList 배열을 추가했다.

조건에 해당하는 땅을 arrList 배열에 입력한 후에 마지막에 arrList 배열의 크기가 2개 이상일 때 평균을 내서 땅의 인구수를 평균으로 변경한다.

 

변경해준 후에는 isMove 변수를 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[][] map;
    static boolean[][] visited;
    static int N, L, R, ans;
    static boolean isMove;
	
    public static class Position {
        int x;
        int y;
		
        public Position(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];
        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());
            }
        }
		
        // 변경한 값이 없을 때까지 반복
        while (true) {
            visited = new boolean[N][N]; // 방문 유부
            isMove = false; // 변경 유무
			
            for (int i=0; i<N; i++) {
                for (int j=0; j<N; j++) {
                    if (!visited[i][j]) bfs(i, j);
                }
            }
			
            if (!isMove) break;
            ans++;
        }
		
        System.out.println(ans);
    }
	
    public static void bfs(int x, int y) {
        Queue<Position> q = new LinkedList<>();
        ArrayList<Position> arrList = new ArrayList<>(); // 인구수를 평균내기 위한 배열
		
        arrList.add(new Position(x, y)); // 시작 땅 추가
        q.add(new Position(x, y));
        visited[x][y] = true;
        int sum = map[x][y];
		
        while(!q.isEmpty()) {
            Position now = q.poll();
			
            for (int i=0; i<4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
				
                if (nx < 0 || nx > N-1 || ny < 0 || ny > N-1 || visited[nx][ny]) continue;
				
                int sumxy = Math.abs(map[nx][ny] - map[now.x][now.y]);
				
                // 조건에 해당하는 땅 (인구수 차이가 L과 R사이)
                if (L <= sumxy && sumxy <= R) {
                    sum += map[nx][ny];
					
                    arrList.add(new Position(nx, ny));
                    q.add(new Position(nx, ny));
                    visited[nx][ny] = true;
                }
            }
        }
		
        // 변경할 값이 존재할 경우
        if (arrList.size() > 1) {
            int num = sum / arrList.size();
            for (int i=0; i<arrList.size(); i++) {
                map[arrList.get(i).x][arrList.get(i).y] = num;
            }
			
            isMove = true;
        }
    }
}