[백준] 16234번. 인구 이동(JAVA)

문제

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

---

풀이(24분)

import java.io.*;
import java.util.*;

class Main {

    static int n, l, r, count, answer;
    static int[][] map;
    static boolean[][] visited;
    static List<Point> points = new ArrayList<>();
    static Queue<Point> queue = new LinkedList<>();
    static int[] dx = new int[]{0, 0, -1, 1};
    static int[] dy = new int[]{-1, 1, 0, 0};
    static boolean flag = false;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        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];
        visited = new boolean[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());
            }
        }

        do{
            flag = false;
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    if(visited[i][j]){ // 이미 체크했다면 패스
                        continue;
                    }
                    visited[i][j] = true; // 방문 체크
                    points.clear(); // points 배열 초기화
                    points.add(new Point(i, j));
                    queue.add(new Point(i, j));
                    count = map[i][j]; // count 값 초기화
                    bfs(); // bfs 시작
                    if(points.size() != 1){ // points의 사이즈가 1이라면 국경이 개방된 적이 없음
                        flag = true;
                    }
                    for(Point p : points){
                        map[p.row][p.col] = count / points.size(); // 소숫점 절삭
                    }
                }
            }
            for(int i = 0; i < n; i++){
                Arrays.fill(visited[i], false); // 방문 배열 초기화
            }
            if(flag){ // 한 국가라도 이동한 적이 있다면 정답 추가
                answer++;
            }
        }while(flag);

        System.out.println(answer);
    }

    static void bfs(){
        while(!queue.isEmpty()){
            Point p = queue.poll();
            int curRow = p.row;
            int curCol = p.col;
            for(int i = 0; i < 4; i++){
                int nextRow = curRow + dx[i];
                int nextCol = curCol + dy[i];
                if(!isInBounds(nextRow, nextCol)){ // 범위 안에 있는지
                    continue;
                }
                if(visited[nextRow][nextCol]){ // 방문한 적이 있는지
                    continue;
                }
                int diff = Math.abs(map[curRow][curCol] - map[nextRow][nextCol]); // 두 국가 간의 인원 수 차이
                if(diff >= l && diff <= r){ // 차이가 범위 안에 들어온다면
                    points.add(new Point(nextRow, nextCol));
                    count += map[nextRow][nextCol];
                    visited[nextRow][nextCol] = true;
                    queue.add(new Point(nextRow, nextCol));
                }
            }
        }
    }

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

    private static boolean isInBounds(int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < n;
    }
}

---

문제 풀이 전략

 

우선 국경을 확인한다. 이 때 union-find를 사용할까 했지만 굳이 복잡하게 쓰기보다는 방문 배열을 통해 중복 체크하지만 않게 하는 것으로 했다.

 

1. 하나의 점에 대해 방문을 확인한 뒤, 국경을 모두 확인한다.

2. 국경이 확인되면 개방될 수 있는지 확인한다.

2-1. 국경이 개방되었다면 개방된 국가에 대해 인구를 통합한다.

2-2. 개방되지 않았다면 방문 체크만 한 뒤 넘어간다.

3. 모든 점에 대해 탐색을 진행하며 국경이 한번이라도 개방된 경우가 있을 때까지만 진행한다.