[BJ]G5 16234 인구이동

BJ G5 16234 인구이동

 

 

문제링크

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

16234번: 인구 이동

 

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

BJ G5 16234 인구이동 DFS - YouTube

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.StringTokenizer;

/**
 * 
 * @author 은서파
 * @since 2021/11/30
 * @see https://www.acmicpc.net/problem/16234
 * @performance 113,504 424 , 최적화 후: 20,880 308
 * @category #완전탐색
 */

public class BJ_G5_16234_인구이동_DFS {

    private static int N, L, R;
    private static int[][] map;

    // 탐색 과정에서 필요한 녀석들
    private static Nation[] nations;// 탐색에 성공한 지점 목록
    private static int nationPop, nationCnt;

    // 사방탐색을 이용한 완탐
    private static int[][] deltas = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
    private static boolean[][] visited;

    // 정답은?
    private static int turnCnt;

    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        input = new BufferedReader(new StringReader(src));
        StringTokenizer tokens = new StringTokenizer(input.readLine());
        N = Integer.parseInt(tokens.nextToken());
        L = Integer.parseInt(tokens.nextToken());
        R = Integer.parseInt(tokens.nextToken());
        map = new int[N][N];
        for (int r = 0; r < N; r++) {
            tokens = new StringTokenizer(input.readLine());
            for (int c = 0; c < N; c++) {
                map[r][c] = Integer.parseInt(tokens.nextToken());
            }
        }
        // 입력 완료

        // 필요한 자원 초기화
        nations = new Nation[N * N]; // 최대 크기 가정
        // 이동이 가능한가?
        boolean isMove = true;
        while (isMove) {
            // 모든 정점을 대상으로 탐색 수행
            isMove = false;// 배수진을 치고!! 한번이라도 이동 가능하면 true로 변경
            visited = new boolean[N][N];

            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    if (!visited[r][c]) {
                        // 미방문인 지점을 중심으로 탐색 시작
                        nationPop = 0;
                        nationCnt = 0;
                        // nations는 여기서 초기화를 하지 않았다!!
                        dfs(r, c);
                        // 지도가 업데이트 될 수 있는 경우는? 국가의 개수가 2이상이라면..
                        if (nationCnt > 1) {
                            // 지도 업데이트
                            int avg = nationPop / nationCnt;
                            for (int i = 0; i < nationCnt; i++) {
                                Nation n = nations[i];
                                map[n.r][n.c] = avg;
                            }

                            isMove = true;
                        }
                    }
                }
            }// 전체 지도에 대한 탐색 종료!!
            if (isMove) {
                turnCnt++;
            }
        }
        System.out.println(turnCnt);
    }

    private static void dfs(int r, int c) {
        visited[r][c] = true;
        nationPop += map[r][c]; // 인구수 증가
        // nations[nationCnt++] = new Nation(r, c);
        addNation(nationCnt++, r, c);

        for (int d = 0; d < deltas.length; d++) {
            int nr = r + deltas[d][0];
            int nc = c + deltas[d][1];

            if (isIn(nr, nc) && !visited[nr][nc]) {
                int diff = Math.abs(map[r][c] - map[nr][nc]);
                if (diff >= L && diff <= R) {
                    dfs(nr, nc);
                }
            }
        }
    }

    private static void addNation(int i, int r, int c) {
        if (nations[i] == null) {
            nations[i] = new Nation(r, c);
        } else {
            nations[i].r = r;
            nations[i].c = c;
        }
    }

    private static boolean isIn(int r, int c) {
        return 0 <= r && r < N && 0 <= c && c < N;
    }

    static class Nation {
        int r, c;

        public Nation(int r, int c) {
            this.r = r;
            this.c = c;
        }

    }

    // REMOVE_START
    private static String src = "3 5 10\n" +
                                "10 15 20\n" +
                                "20 30 25\n" +
                                "40 22 10";
    // REMOVE_END
}