[Algorithm] SW 기출문제 - 인구 이동(16234) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 백준 SW 기출문제 인구 이동 자바 풀이를 진행하고자 합니다.

 

문제 출처: https://www.acmicpc.net/problem/16234

16234번: 인구 이동

 

 

1. 풀이 소스

 

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N = parseInt(st.nextToken());
        int L = parseInt(st.nextToken());
        int R = parseInt(st.nextToken());
        
        PeopleMove pm = new PeopleMove(N, L, R);
        
        for (int row = 0; row < N; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 0; col < N; col++) {
                pm.setMap(row, col, parseInt(st.nextToken()));
            }
        }
        
        pm.run();
        System.out.println(pm.getDays());
    }
}

class PeopleMove {
    
    static final int[] DR = {-1, 0, 1, 0};
    static final int[] DC = {0, -1, 0, 1};
    
    int n; //  n by n 행렬
    int low; // 인구 차이 R 이하의 R
    int high; // 인구 차이 L 이상의 L
    int[][] map;
    int result; // 결과
    int currentPeopleCnt; // dfs  로얻은 현재 인구 수
    List<Point> current; // 현재 dfs에 적용할 때, 인구 이동해야하는 포인트
    boolean[][] visited; // 방문
    
    PeopleMove (int n, int low, int high) {
        map = new int[n][n];
        visited = new boolean[n][n];
        
        this.n = n;
        this.low = low;
        this.high = high;
    }
    
    void setMap(int row, int col, int value) {
        map[row][col] = value;
    }
    
    void run() {
        
        while(true) {
            int breakPoint = 0; // 만약 current.size() == 1 이라면 (인구 이동 X) breakPoint++ 하여 n * n 개수와 같은지 판단
            for (int row = 0; row < n; row++) {
                for (int col = 0; col < n; col++) {
                    current = new ArrayList<>(); // dfs에 적용할 current 리스트
                    currentPeopleCnt = 0; // 0 초기화
                    dfs(row, col); // dfs
                    
                    // 국경선이 닫힌 것이므로 이제 인구이동 시작하기 
                    if (current.size() > 1) {
                        int avgPeopleCnt = currentPeopleCnt / current.size();
                        for (Point p : current) map[p.row][p.col] = avgPeopleCnt; // 인구 평균으로 업데이트
                    } else breakPoint++; // 만약 모든 dfs가 하나씩만 나오게 되는 경우
                }
            }

            
            if (breakPoint == n * n) break; // 인구 이동할 수 없으므로 종료
            result++; // 인구 이동 가능하므로 횟수 ++
            for (int row = 0; row < n; row++) Arrays.fill(visited[row], false); //dfs 결과 초기화
        }
    }

    void dfs(int row, int col) {
 
        if (visited[row][col]) return; // 만약 방문한 경우 return
        visited[row][col] = true; // 방문 표시
        
        currentPeopleCnt += map[row][col]; // currentPeopleCnt 전역변수에 ++
        current.add(new Point(row, col)); // current 리스트에 추가
        
        for (int k = 0; k < 4; k++) {
            int nextR = row + DR[k];
            int nextC = col + DC[k];
            if (!isValid(row, col, nextR, nextC)) continue;
            dfs(nextR, nextC); // 재귀
        }
    }
    
    // 현재 행, 열 --- 지금 행, 열 비교 인덱스 유효하고, 인접한 두 좌표가 low <= 차이 <= high 여야 함
    boolean isValid(int preRow, int preCol, int nowRow, int nowCol) {
        return nowRow >= 0 && nowRow < n && nowCol >= 0 && nowCol < n 
            && Math.abs(map[preRow][preCol] - map[nowRow][nowCol]) <= high
            && Math.abs(map[preRow][preCol] - map[nowRow][nowCol]) >= low;
    }
    
    int getDays() {
        return result;
    }
    
    static class Point {
        int row;
        int col;
        
        Point (int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}

 

 

2. 풀이 중점 사항

 

해당 문제는 2차원 포문에서 인구 이동이 가능한 그룹 하나당 result++가 아니라,

2중 포문이 모두 종료되어 인구 이동이 가능한 그룹의 리스트들이 모두 처리된 후가 result++입니다.

 

void run() {

    while(true) {
        int breakPoint = 0; // 만약 current.size() == 1 이라면 (인구 이동 X) breakPoint++ 하여 n * n 개수와 같은지 판단
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {
                current = new ArrayList<>(); // dfs에 적용할 current 리스트
                currentPeopleCnt = 0; // 0 초기화
                dfs(row, col); // dfs

                // 국경선이 닫힌 것이므로 이제 인구이동 시작하기 
                if (current.size() > 1) {
                    int avgPeopleCnt = currentPeopleCnt / current.size();
                    for (Point p : current) map[p.row][p.col] = avgPeopleCnt; // 인구 평균으로 업데이트
                } else breakPoint++; // 만약 모든 dfs가 하나씩만 나오게 되는 경우
            }
        }


        if (breakPoint == n * n) break; // 인구 이동할 수 없으므로 종료
        result++; // 인구 이동 가능하므로 횟수 ++
        for (int row = 0; row < n; row++) Arrays.fill(visited[row], false); //dfs 결과 초기화
    }
}

따라서, 위의 코드처럼 current.size()가 1보다 크다면, 즉 인구 이동이 가능한 도시가 있다면 인구 이동을 처리한 후, 

모든 탐색이 끝난 후 breakPoint를 확인 후 result를 업데이트하는 방식입니다.

 

void dfs(int row, int col) {

    if (visited[row][col]) return; // 만약 방문한 경우 return
    visited[row][col] = true; // 방문 표시

    currentPeopleCnt += map[row][col]; // currentPeopleCnt 전역변수에 ++
    current.add(new Point(row, col)); // current 리스트에 추가

    for (int k = 0; k < 4; k++) {
        int nextR = row + DR[k];
        int nextC = col + DC[k];
        if (!isValid(row, col, nextR, nextC)) continue;
        dfs(nextR, nextC); // 재귀
    }
}

 

dfs를 활용하여, 인접한 도시가 인구 이동이 가능하다면 재귀를 진행함으로써, 방문 여부를 체크할 수 있습니다. 

따라서, 2중 포문으로 방문 처리된 위치에 도착하더라도 이미 방문되었기 때문에 바로 return 하여 current.size() == 1을 유지할 수 있습니다.

 

만약 모든 도시가 인구 이동이 더 이상 불가능하다면 isValid()가 false가 되어 모든 도시는 전부 current.size() == 1이 되게 됩니다.

도시의 current.size() == 1이라면 breakPoint를 ++ 하므로, while문의 종료 조건을 만족할 수 있게 됩니다.

 

이상으로 인구 이동 자바 풀이를 마치도록 하겠습니다. 감사합니다.!