[BOJ] 16234 인구이동 - Java

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

16234번: 인구 이동

 

[풀이]

dfs를 이용하여 몇 개의 뭉텅이로 이루어져있는지를 구하는 것을 응용하는 문제였다.

생각할 부분은

1. 하루 동안에 인구이동이 일어날 때 어느 지역들이 연합을 이루는지, 각 연합의 sum

  -> AllArr 과 sumArr 에 각각의 값들을 담았다.

2. 총 몇일이 지날지

  -> 하루 동안 인구이동이 일어나는지 볼 때 인구의 차이가 L<= <=R이면 flag를 true로 설정하게 한 후, flag를 관찰한다.

       (flag가 true면 인구이동이 한 번이라도 일어난 것 -> 다음날로 고고 , false면 한 번도 일어나지 않은 것 -> break)

나머지는 코드 주석으로 확인하자

3. 각 변수의 초기화 지점

answer -> 총 몇 일이 지났는지를 확인하는 변수이므로 while문 밖에서 초기화한다.

flag, sumArr, AllArr, visit -> 하루 동안의 인구 이동에서 쓰이는 변수들이므로 while문 안에서 초기화한다.

sum, Arr -> 한 연합에서 쓰이는 변수이므로 이중 for문 안에서 초기화해준다.

 

[코드]

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

public class Boj16234_인구이동 {
    static StringTokenizer st;
    static int N,L,R;
    static int[][] Map;
    static int[] dRow = {-1,1,0,0};
    static int[] dCol = {0,0,-1,1};

    static boolean flag = true;

    static boolean[][] visit;
    static ArrayList<Integer> sumArr = new ArrayList<>();
    static ArrayList<ArrayList<Point>> AllArr = new ArrayList<>();

    static int sum = 0;
    static ArrayList<Point> Arr = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("src/main/java/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        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문 시작
        int answer = 0; //총 몇일지났는지
        while (true) {
            //flag 확인
            if (!flag) { //한 번도 인구이동이 일어나지 않았으면 break
                break;
            }
            //새로운 날이 시작되었으므로 변수 초기화
            AllArr = new ArrayList<>();
            sumArr = new ArrayList<>();
            flag = false;
            visit = new boolean[N][N];
            answer++;

            //Map을 살피면서 어디가 연합을 이루고 있는지 보기
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visit[i][j]) { //방문하지 않은 점에 대해
                        visit[i][j] = true; //방문 설정
                        Arr = new ArrayList<>(); //한 연합에 대해 초기화 (어느 지역이 포함되어있는지)
                        Arr.add(new Point(i, j)); //첫 방문 지역 추가
                        sum = Map[i][j]; //한 연합에 대해 초기화(sum이므로 처음 인구값으로)

                        dfs(i, j, 0); //연합 확인 고고

                        AllArr.add(Arr); //연합 확인됐으면 걔네들을 AllArr에 넣음
                        sumArr.add(sum);
                    }
                }
            }

            //하루 끝났으니까 AllArr 보면서 -> Map 갱신
            for (int i = 0; i < AllArr.size(); i++) { //연합 덩어리마다
                for (int j = 0; j < AllArr.get(i).size(); j++) { //한 연합에 속해있는 지역들 Map 갱신
                    Point point = AllArr.get(i).get(j);
                    Map[point.row][point.col] = sumArr.get(i) / AllArr.get(i).size();
                }
            }
        }
        System.out.println(answer-1); //마지막 안움직인 날 체크한거는 빼고 날짜 세기(-1)
    }

    static void dfs(int row, int col, int count){
        for(int i=0;i<4;i++){
            int newRow = row + dRow[i];
            int newCol = col + dCol[i];
            if(0<=newRow && newRow <N && 0<=newCol && newCol <N){ //범위 체크
                if(!visit[newRow][newCol]){ //방문하지 않았으면
                    int diff = Math.abs(Map[row][col] - Map[newRow][newCol]); //인구차이
                    if(L<=diff && diff <=R){ //인구차이 범위 체크, L이상 R이하면 연합으로 인정
                        visit[newRow][newCol] = true; //연합이니까 방문처리
                        Arr.add(new Point(newRow,newCol)); //연합이니까 Arr에 추가
                        sum+=Map[newRow][newCol]; //sum 추가
                        dfs(newRow,newCol,count+1); //다음 연합 찾으러 고고씽
                        flag = true; //국경 하나라도 열림
                    }
                }
            }
        }
    }

    static class Point{
        int row;
        int col;

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

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

}

[느낀점]

소요시간 : 50min

로직 생각하면서는 아 복잡하다..했는데 한 번에 딱 풀려서 너무 기분 좋았다

이렇게만 가자!!