백준 16234 인구 이동

문제

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

---

입출력

---

예제

---

태그

• 구현
• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 시뮬레이션

---

풀이

• bfs를 이용해 풀이한다.

• 주어진 값을 저장하는 이차원 배열 map과 방문처리를 위한 이차원 배열 visited를 이용한다.

• 전체 map을 돌면서 주어진 조건에 맞춰서 bfs를 진행하는데 주의점은 전체 map을 대상으로 한 bfs가 끝나도 값을 재수정한 후 다시 전체 map을 기준으로 bfs를 해야한다.

• 또한 값을 재수정한 후 visited 배열 또한 초기화를 해주어야 한다.

• cnt라는 이동 횟수를 정해 놓은 후 이 값이 1 이상이면 이동이 일어난 것으로 보고 bfs를 계속 진행하여 탐색을 하지만 0이라면 더 이상 이동할 수 없다는 것을 뜻함으로 종료한다.

---

코드

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;

/**
 * 16234_인구 이동
 *
 * 틀린 이유 : map 전체 좌표를 대상으로 bfs를 진행할 때 값이 바뀌면 다시 처음부터 bfs를 진행해야 한다.
 */
public class P_16234 {
    static int N, L, R;
    static int[][] map;
    static boolean[][] visited; // 방문처리를 위한 배열(초기화 필수)
    static int[] mx = {-1,1,0,0};
    static int[] my = {0,0,-1,1};

    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];
        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());
            }
        }
        
        // 답 구하기

        int answer = 0;
        boolean flag = true;

        while(flag) {
            // 이동을 더 이상 못하면
            if (bfs() == 0) {
                flag = false;
            }
            else {
                answer++;
            }
        }

        System.out.println(answer);

    }

	// bfs를 이용한 탐색 진행 -> cnt를 반환한다.
    static int bfs(){
        // 이동할 수 있는 횟수를 구한다.
        // 0이면 이동이 없다는 뜻, 0 초과이면 이동이 있다는 뜻이다.
        int cnt = 0;

        // bfs만을 구현하지 않고 전체 map을 돌 때마다 bfs를 하는 식으로 구현했다.
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(!visited[j][i]) {
                    visited[j][i] = true;

                    Queue<Point> queue = new LinkedList<>();
                    queue.add(new Point(j, i));

                    // 이동 가능한 좌표들의 평균값을 구해서 그 좌표에 해당하는 값들을 바꿔줘야 한다.
                    // 그러기 위해 좌표들을 저장하는 ArrayList
                    ArrayList<Point> list = new ArrayList<>();
                    list.add(new Point(j, i));

                    // 이동 가능한 좌표들 값들의 합
                   int sum = map[j][i];

                    while (!queue.isEmpty()) {
                        Point p = queue.poll();

                        for (int m = 0; m < 4; m++) {
                            int y = p.y + my[m];
                            int x = p.x + mx[m];

                            if(0<=x&&x<N && 0<=y&&y<N) {
                                if(!visited[y][x] && isPossible(p.x, p.y, x, y)) {
                                    visited[y][x] = true;
                                    queue.add(new Point(y,x));
                                    list.add(new Point(y,x));
                                    sum += map[y][x];
                                    cnt++;
                                }
                            }
                        }
                    }

                    // 이동을 한 번 이상이라도 했으면
                    if(cnt > 0) {
                        int avg = sum / list.size();

                        for (int k = 0; k < list.size(); k++) {
                            map[list.get(k).y][list.get(k).x] = avg;
                        }
                    }
                }
            }
        }

        // map 전체를 돌아서 이동이 끝났으면 초기화 해주어야 한다.
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                visited[j][i] = false;
            }
        }
        return cnt;
    }

    // 주어진 조건에 따라 이동할 수 있는지 확인하는 메서드
    static boolean isPossible(int currentX, int currentY, int nextX, int nextY) {
        int val = Math.abs(map[currentY][currentX] - map[nextY][nextX]);

        if(L<=val && val<=R){
            return true;
        }
        return false;
    }

    static class Point {
        int y;
        int x;

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