[백준 16234번][Java] 인구 이동 - 그래프 탐색, 구현

www.acmicpc.net/problem/16234

16234번: 인구 이동

 

그래프 탐색을 이용한 구현 문제였습니다.

 

풀이 방식

1. 전체 나라에 대해서 DFS하면서 인구 이동이 가능한 나라끼리 그룹으로 묶어 줍니다.

2. 1에서의 정보를 바탕으로 같은 그룹의 나라들의 값을 갱신합니다.

2번이 끝나고 다시 1번을 수행합니다.

 

그룹으로 묶어 주는 과정에서 그 어떠 나라도 국경을 열지 않았다면 그룹의 개수를 N*N개가 됩니다. 

각 그룹은 자기 자신을 포함하는 그룹이 되겠지요. 이를 종결 조건으로 해줍니다.

 

구현 세부 사항

 

1번 과정

그룹핑 방식은 List에 해당 나라의 좌표를 저장하도록 구현했습니다. 좌료를 저장해두면 다시 인구수를 갱신하는 과정에서 탐색 과정 없이 좌표를 이용해 바로 갱신이 가능하기 때문입니다. 그리고 나라의 수도 최대 2500이므로 메모리도 충분하고요. 그리고 2번 과정에서 계산이 편하도록 그룹의 총 인구수를 계산해 따로 저장합니다.

 

2번 과정

1번 과정의 값들을 이용해 갱신할 값을 계산후 저장된 좌표를 순회하면서 나라의 인구수를 갱신합니다.

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int N,L,R;
    static int[][] countries;
    public static void main(String[] args) throws IOException {
        InputReader reader = new InputReader();
//        InputReader reader = new InputReader("testcase.txt");
        StringTokenizer st = new StringTokenizer(reader.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        countries = new int[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(reader.readLine());
            for (int j = 0; j < N; j++) {
                countries[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int count = 0;
        while(true) {
            List<List<Country>> groupList = new ArrayList<>();
            List<Integer> populationList = new ArrayList<>();
            grouping(groupList, populationList);

            if(groupList.size() == N*N) break;
            allocate(groupList, populationList);
            count++;
        }
        System.out.println(count);
    }

    private static void grouping(List<List<Country>> groupList, List<Integer> populationList) {
        boolean[][] visited = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(!visited[i][j]) {
                    List<Country> group = new ArrayList<>();
                    int totalPopulation = findSameGroupCountry(i,j, group, visited);
                    populationList.add(totalPopulation);
                    groupList.add(group);
                }
            }
        }
    }

    static int[] dr = {0,0,1,-1};
    static int[] dc = {1,-1,0,0};
    private static int findSameGroupCountry(int row, int col, List<Country> group, boolean[][] visited) {
        visited[row][col] = true;
        group.add(new Country(row, col));
        int total = countries[row][col];
        for (int i = 0; i < 4; i++) {
            int nextRow = row+dr[i]; int nextCol = col+dc[i];
            if(isRange(nextRow, nextCol) && !visited[nextRow][nextCol]) {
                int diff = Math.abs(countries[row][col] - countries[nextRow][nextCol]);
                boolean canMove = diff >= L && diff <= R;
                if(canMove) {
                    total += findSameGroupCountry(nextRow, nextCol, group, visited);
                }
            }
        }
        return total;
    }

    private static void allocate(List<List<Country>> groupList, List<Integer> populationList) {
        for (int i = 0; i < groupList.size(); i++) {
            List<Country> group = groupList.get(i);
            int val = populationList.get(i)/group.size();
            if(group.size() <= 1) continue;
            for (int j = 0; j < group.size(); j++) {
                Country country = group.get(j);
                countries[country.row][country.col] = val;
            }
        }
    }


    private static boolean isRange(int r, int c) {
        if(r < 0 || r >= N || c < 0 || c >= N) return false;
        return true;
    }

}
class Country {
    int row, col;

    public Country(int row, int col) {
        this.row = row;
        this.col = col;
    }

    @Override
    public String toString() {
        return "Country{" +
                "row=" + row +
                ", col=" + col +
                '}';
    }
}

class InputReader {
    private BufferedReader br;

    public InputReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    public InputReader(String filepath) {
        try {
            br = new BufferedReader(new FileReader(filepath));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    public List<Character> readLineIntoCharList() throws IOException {
        List<Character> l = new ArrayList<>();
        while(true) {
            int readVal = br.read();
            if(readVal == '\n' || readVal == -1) break;
            l.add((char)readVal);
        }
        return l;
    }

    public boolean ready() throws IOException {
        return br.ready();
    }

    public String readLine() throws IOException {
        return br.readLine();
    }
    public int readInt() throws IOException {
        return Integer.parseInt(readLine());
    }
    public Long readLong() throws IOException {
        return Long.parseLong(readLine());
    }
}