[BOJ] 백준 16234 - 인구 이동 풀이

1. 문제

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

16234번: 인구 이동

2. Error Point

• 이중 반복문을 빠져 나오는 경우에서 생각하기 오래 걸렸다.
  • flag 변수를 하나 두어서 이중 반복문을 빠져 나오는 것이 아닌 실제 값을 더하는 부분에서 처리하자
    
    
    

3. 풀이 Point

• 도시의 좌표, 인구 수를 멤버 변수로 가지는 static class를 만든다.
• 주요 변수 및 자료구조
  • visited 배열 : BFS 탐색을 위한 방문 배열
  • cityList : 인구를 이동시킬 수 있는 도시 객체를 저장할 리스트
  • isPersonMoveFlag : 인구 이동이 가능한지를 판단하는 플래그
  • result : 지난 날짜 (출력 값)
• 입력 값을 받은 후 인구이동이 가능한 도시가 없을 때까지 while 무한 반복을 돌면서 판단한다.
  • 이중 for문을 통해 BFS 출발 지점을 정한다.
  • BFS 함수를 실행한다.
    • 상하좌우를 보면서 선택 객체와의 인구 차이가 L이상 R이하인 도시를 cityList에 넣는다.
    • 만약 cityList에 넣을 수 있다면 isPersonMoveFlag를 true로 만든다.
    • 만약 cityList에 넣을 수 있다면 list에 있는 값의 평균을 구한 후 리스트에 있는 도시의 인구수를 방금 구한 평균으로 바꾼다.
  • 인구가 이동할 수 있었다면 (즉 isPersonMoveFlag가 true라면) 하루가 지난 것이기 때문에 result를 하나 증가시킨다.
    
    
    

4. 소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    static int N, L, R;
    static int[][] map;

    static boolean[][] visited;

    static class City {
        int x;
        int y;
        int val;

        public City(int x, int y, int val) {
            this.x = x;
            this.y = y;
            this.val = val;
        }
    }
    static List<City> cityList;
    static boolean isPersonMoveFlag = false;

    static int result = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        while (true) {
            visited = new boolean[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    cityList = new ArrayList<>();
                    if (!visited[i][j]) {
                    	personMoveBFS(i, j);
                    }
                }
            }

            if (isPersonMoveFlag) {
                result += 1;
            } else {
                break;
            }

            isPersonMoveFlag = false;
        }

        bw.write(Integer.toString(result));
        bw.flush();
        bw.close();
        br.close();
    }

    private static void personMoveBFS(int x, int y) {
        Queue<City> q = new ArrayDeque<>();
        q.add(new City(x, y, map[x][y]));

        visited[x][y] = true;
        cityList.add(new City(x, y, map[x][y]));

        while (!q.isEmpty()) {
            City poll = q.poll();

            for (int p = 0; p < 4; p++) {       // 위 아래 오 왼
                int xf = poll.x + dx[p];
                int yf = poll.y + dy[p];

                if (xf >= 0 && xf < N && yf >= 0 && yf < N && !visited[xf][yf]) {
                    int tempSum = Math.abs(poll.val - map[xf][yf]);
                    if (tempSum != 0 && tempSum >= L && tempSum <= R) {
                        visited[xf][yf] = true;
                        City city = new City(xf, yf, map[xf][yf]);

                        isPersonMoveFlag = true;

                        cityList.add(city);
                        q.add(city);
                    }
                }
            }
        }

        if (isPersonMoveFlag) {
            int sum = 0;
            for (int p = 0; p < cityList.size(); p++) {
                sum += cityList.get(p).val;
            }

            int input = sum / cityList.size();
            for (int p = 0; p < cityList.size(); p++) {
                City city = cityList.get(p);
                map[city.x][city.y] = input;
            }
        }
    }
}

5. 배운점

• 이중 반복문을 빠져나오기 어렵다면 flag 변수를 하나 두어서 이중 반복문을 빠져 나오는 것이 아닌 실제 값을 더하는 부분에서 처리하자
  
  
  

6. 점수

60/100