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

문제에 나와있는 대로 구현하면 풀리는 정직한 시뮬레이션 문제

16234번: 인구 이동

 

풀이

처음에 문제가 애매하다는 생각이 들었다. 이차원배열을 map이라 하면 map에 따로 떨어진 두 집단이 있을경우 이걸 각각 인구 이동횟수로 세야하는지 아니면 한 round당 횟수로 해야하는지 몰랐다.

 

 

그래서 질문게시판을 참고하니 후자인 한 round당으로 세는게 맞았다. 즉, map에서 인구 이동이 가능한 집단이 여러 개가 있어도 한 번으로 치는 것이다.

 

 

우선 BFS를 해야하므로 방문체크 배열을 두었다. 인구 이동이 더이상 없는 경우를 알려주는 boolean flag 변수를 두었다. 인구 이동 결과를 저장할 임시 이차원 배열을 두는데, 인구 수의 범위가 0~100이므로 Arrays.fill method를 이용하여 -1로 초기화 해놓는다.

 

 

인구 이동을 할 후보군 좌표 저장을 위해서 BFS용 큐 말고 candidate라는 큐를 하나 더 두었다. 이 candidate 큐에 element를 추가할 때 마다 해당 좌표의 인구 수를 미리 더해서 합을 저장한다.

 

 

처음에 자기 자신을 큐에 포함하기 때문에 candidate 큐의 크기가 2 이상이라면 인구 이동이 가능하므로 임시로 만든 이차원 배열에 이동된 인구 수를 저장한다. 이때 이동이 일어났다면 flag 변수값을 true로 설정한다.

 

 

모든 map 좌표 탐색이 끝난 이후 flag값이 false일 경우 while문을 break하고 최종 인구이동 횟수를 출력한다.

그렇지 않으면 임시로 만든 이차원 배열 값을 원래 map에 옮긴다.

 

Logic

1. while문 시작시 flag, visited, temp를 초기화한다.
2. 이중 for문을 돌며 방문하지 않은 곳이라면 BFS 탐색을 시작한다. sum값은 시작좌표 인구값으로 초기화한다.
   1. solve(): 현재 좌표값과 다음으로 갈 수 있는 좌표값 차이가 \[L, R\]이라면 BFS 큐 뿐만 아니라 candidate 큐에도 저장한다. 이때 sum값에 다음 좌표값을 더해준다.
   2. movePeople(): BFS탐색 이후 candidate 큐 크기가 2 이상이면 flag = true로 표시하고 임시배열인 temp에 인구이동 결과값을 저장한다. candidate 큐는 비워준다.
   3. migrate(): flag = true이면 map을 temp값으로 바꾼다. 만약 temp값이 -1일땐 인구 이동이 일어나지 않은 것이므로 바꾸지 않는다.
3. flag == false이면 인구이동이 일어나지 않았다는 뜻이므로 while문을 break한다.
4. 인구이동 횟수를 출력한다.

 

코드

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

public class Main {
    static int N, L, R, move, sum;
    static int[] pos_x = { 1, 0, -1, 0 };
    static int[] pos_y = { 0, 1, 0, -1 };
    static int[][] map, temp;
    static boolean[][] visited;
    static boolean flag;
    static Queue<Coord> candidate = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        map = new int[N + 2][N + 2];

        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(true) {
            flag = false;
            visited = new boolean[N + 2][N + 2];
            temp = new int[N + 2][N + 2];
            for (int[] row : temp)
                Arrays.fill(row, -1);

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(!visited[i][j]) {
                        visited[i][j] = true;
                        solve(i, j);

                        if (candidate.size() > 1) {
                            flag = true;
                            movePeople();
                        }
                        candidate.clear();
                    }
                }
            }

            if (!flag) break;
            migrate();
            move++;
        }

        System.out.println(move);
        br.close();
    }

    public static void movePeople() {
        int avg = sum / candidate.size();

        while(!candidate.isEmpty()) {
            int x = candidate.peek().x;
            int y = candidate.peek().y;
            candidate.poll();

            temp[x][y] = avg;
        }
    }

    public static void migrate() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (temp[i][j] == -1) continue;
                map[i][j] = temp[i][j];
            }
        }
    }

    public static void solve(int i, int j) {
        Queue<Coord> q = new LinkedList<>();

        q.offer(new Coord(i, j));
        candidate.offer(new Coord(i, j));
        sum = map[i][j];

        while(!q.isEmpty()) {
            int x = q.peek().x;
            int y = q.peek().y;
            q.poll();

            for (int d = 0; d < 4; d++) {
                int nx = x + pos_x[d];
                int ny = y + pos_y[d];
                if (nx < 0 || nx >= N || ny < 0 || ny >= N || visited[nx][ny]) continue;

                int diff = Math.abs(map[nx][ny] - map[x][y]);
                if (diff < L || diff > R) continue;

                visited[nx][ny] = true;
                q.offer(new Coord(nx, ny));
                sum += map[nx][ny];
                candidate.offer(new Coord(nx, ny));
            }
        }
    }

    static class Coord {
        int x;
        int y;

        public Coord(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

}

실행 결과