백준 16234번 : 인구 이동 java

이 문제는 데이터들을 입력 받아서 주변과의 차이가 L 이상, R  이하라면 각각의 셀에 있는 값들을 모두 더해서 평균값으로 만들어주는 알고리즘입니다.

예제 1번을 보시면 이를 더 잘 이해하실 수 있습니다.

코드를 보면서 추가로 설명해드리도록 하겠습니다.

---

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

public class Main {
    static int N, L, R;
    static int[] dR = {1, -1, 0, 0};
    static int[] dC = {0, 0, 1, -1};
    static int[][] map;

    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][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());
        }

        int day = 0;
        while(populationMove() != -1)
            day++;

        System.out.println(day);
    }

    static int populationMove(){
        boolean[][] visited = new boolean[N][N];
        boolean moved = false;

        for(int i = 0; i<N; i++){
            for(int j = 0; j<N; j++){
                if(visited[i][j])
                    continue;

                //연결되어 있는지 확인
                Queue<Node> check = new LinkedList<>();
                //연결된 부분들의 map을 같은 수로 맞추어주기 위해서 생성
                Queue<Node> change = new LinkedList<>();

                check.offer(new Node(i, j));
                int sum = 0;
                int count = 0;

                while(!check.isEmpty()) {
                    Node a = check.poll();
                    change.offer(a);
                    visited[a.row][a.col] = true;

                    count++;
                    sum += map[a.row][a.col];

                    for (int k = 0; k < 4; k++) {
                        int dr = a.row + dR[k];
                        int dc = a.col + dC[k];

                        if (dr < 0 || dc < 0 || dr >= N || dc >= N)
                            continue;
                        if (visited[dr][dc])
                            continue;

                        int gap = Math.abs(map[a.row][a.col] - map[dr][dc]);

                        if(gap>=L && gap<=R) {
                            check.offer(new Node(dr, dc));
                            visited[dr][dc] = true;
                            moved = true;
                        }
                    }
                }
                //저장된 나라의 인구들을 초기화
                while(!change.isEmpty()){
                    Node a = change.poll();
                    map[a.row][a.col] = sum/count;
                }
            }
        }

        if(!moved)
            return -1;
        else
            return 1;
    }
}
class Node{
    int row, col;

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

저는 populationMove 함수에서 map 배열의 각각의 칸들을 돌아다니면서 어디까지 연결이 되어있나 먼저 확인했습니다.

확인 한 다음 연결되어 있는 칸들을 전부 평균값으로 만들어주어야 하기 때문에 sum과 count 변수를 만들었습니다.

또한 change 큐에 이 칸들을 넣어 초기화해주었습니다.

 

이 문제를 풀 때 조심해야 하는 점이 있습니다.

populationMove 함수에서 while 문을 돌 때 아래와 같이 visited를 초기화해줍니다.

Node a = check.poll();
change.offer(a);
visited[a.row][a.col] = true;

그러나 이 while문 안에서도 다음 부분에서는 visited를 먼저 초기화해주어야 합니다.

if(gap>=L && gap<=R) {
    check.offer(new Node(dr, dc));
    visited[dr][dc] = true;
    moved = true;
}

이 이유에 대해서 설명드리겠습니다.

위와 같은 상황이 있다고 가정하겠습니다.

L은 10이고 R은 20입니다.

check 큐에 10이 먼저 들어온다고 두겠습니다.

그럼 위의 그림과 같이 20과 30또한 check 큐에 들어오게 됩니다.

그리고 20과 30이 순서대로 주변의 노드들을 확인하게 됩니다.

20이 들어 있는 노드를 우선 탐색한다고 하겠습니다.

20 노드가 check에서 제거됨과 동시에 visited 배열에서 20이 true가 됩니다.

그리고 주변을 탐색하면서 40이 들어있는 노드를 check에 넣습니다.

20의 주변에는 이제 더 탐색할 노드가 없기 때문에 반복문을 종료합니다.

이제 30이 check 큐에서 제거되면서 visited가 true가 됩니다.

그리고 30 주변의 노드들을 확인하는데 이때 40 노드의 visited 값이 false이기 때문에 40 노드를 다시 한번 check 배열에 추가하게 됩니다.

이런 상황에서 sum과 count에는 40이 들어있는 노드가 한번 더 더해지게 됩니다.

따라서 이러한 상황이 일어나지 않게 하기 위해서는 아래와 같이 check에 추가하면서 바로 visited를 true로 바꾸어주어야 합니다.

if(gap>=L && gap<=R) {
    check.offer(new Node(dr, dc));
    visited[dr][dc] = true;
    moved = true;
}