[골드4, BFS] 백준 16234 - 인구이동 (자바)

Think

1. BFS인데 약간의 조건을 고려해야하는 문제

2. 연합이 있는 경우 전체 BFS를 한번 더 진행해야해서 이를 파악하기 위한 isPossibleContinue을 잘 활용해야 했음 (While문 탈출 조건으로 활용해야해서)

3. 최적화 고려하면 더 좋은 문제 (ex. 연합 있는 경우만 BFS 진행) 

 

 

제출코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class test {
    static int N, L, R, map[][];
    static boolean isVisited[][], isPossibleContinue;
    static int[] dr = new int[]{0, 0, -1, 1};
    static int[] dc = new int[]{-1, 1, 0, 0};
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        init();

        process();
    }

    private static void process() {
        int count = 0;

        while (true) {
            isPossibleContinue = false;

            isVisited = new boolean[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!isVisited[i][j]) {
                        bfs(i, j);
                    }
                }
            }
            if (!isPossibleContinue) break;

            count++;
        }
        System.out.println(count);


    }

    private static void bfs(int r, int c) {
        boolean existUnion = false;

        for (int i = 0; i < 4; i++) {
            int mr = r + dr[i];
            int mc = c + dc[i];

            if (mr < 0 || mc < 0 || mr >= N || mc >= N || isVisited[mr][mc]) continue;

            int humanGap = Math.abs(map[r][c] - map[mr][mc]);
            if (humanGap < L || humanGap > R) continue;

            existUnion = true;
            break;
        }


        // 연합 있는 경우에만 진행하기.
        if (existUnion) {

            //연합이 한번이라도 있으면 전체 bfs 한번 더 해야하니 true
            isPossibleContinue = true;

            Queue<int[]> q = new LinkedList<>();
            Queue<int[]> nationsPosition = new LinkedList<>();
            int totalPopulation = 0;

            q.add(new int[]{r, c});
            isVisited[r][c] = true;

            while (!q.isEmpty()) {
                int[] position = q.poll();
                totalPopulation += map[position[0]][position[1]];
                nationsPosition.add(new int[]{position[0], position[1]});

                for (int i = 0; i < 4; i++) {
                    int mr = position[0] + dr[i];
                    int mc = position[1] + dc[i];

                    if (mr < 0 || mc < 0 || mr >= N || mc >= N || isVisited[mr][mc]) continue;

                    int humanGap = Math.abs(map[position[0]][position[1]] - map[mr][mc]);
                    if (humanGap < L || humanGap > R) continue;

                    q.add(new int[]{mr, mc});
                    isVisited[mr][mc] = true;
                }
            }


            if (nationsPosition.size() >= 2) {

                int newPopulation = totalPopulation / nationsPosition.size();

                while (!nationsPosition.isEmpty()) {
                    int[] p = nationsPosition.poll();
                    map[p[0]][p[1]] = newPopulation;
                }
            }
        }
    }


    public static void init() throws IOException {
        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());
            }
        }
    }

}