[ Baekjoon - 10/04 ] - 16234번: 인구 이동

• 문제 링크 : https://www.acmicpc.net/problem/16234

16234번: 인구 이동

 

• 소요 시간 : 1시간 30분

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 2초
     • 메모리 : 512MB
   • 문제
     • NxN 면적의 땅(1≤N≤50), 땅은 1x1개의 칸으로 나뉘어짐
     • 각 땅(1x1)에는 나라가 하나씩 존재하고 A[r][c]명이 살고있음
     • 인구이동이 불가할때까지 밑의 일들이 반복해서 일어남
       1. 국경선을 공유하는 두 나라의 인구차이가 L이상 R이하인 모든곳의 국경선을 하루간 연다
       2. 국경선이 열려 연합국이 된 나라는 연합의 인구 수/땅 수로 인구가 나눠진다(소수이하는 버림)
       3. 국경선을 닫는다.
     • 위 루틴이 며칠동안 발생하는지 출력하는 문제이다.
   • 이해
     • 문제에서 자세히 서술해줬지만 이해가 힘들어서 그림으로 그리며 흐름을 파악했다.
2. 문제를 익숙한 용어로 재정의와 추상화

   • 

   • 좌측 상단부터 오른쪽으로 문제에서 주어진 시나리오에 맞게 그려보았다. 
3. 문제를 어떻게 해결할 것인가
   • 처음에 어떻게 국경선을 저장할지 고민을 많이했던 것 같다.. 국경선의 개수를 세어보고 배열을 어떻게 잡아야 가독성과 쓰임새를 잘 잡을수있을지 생각하다가, ArrayList에 갈수있는 영역을 담아놓고 사람 분배할때 반복문 쓰는방식으로 쓰는게 생각보다 단순하고 깔끔하게 나을것 같다고 판단해서 관뒀다. ㅋㅋ

   • 

   • 1st 접근 - 영역별로 다른 숫자를 매기면서 BFS 탐색을 전체 map에 대해 돌린 후에 한번에 인구를 분배 )
     • 위 그림처럼 실제 인구 수가 담긴 map과, 방문여부를 저장할 vis 배열을 둘다 정수형으로 선언하고
       vis의 경우, 0이면 방문하지않았고 0이아닌 양의정수이면 방문을 한 경우이다.
       현재 방문하고있는곳을 n으로 주었다면 vis에 기록된 정수는 0~n의 정수이게 된다.
     • 하지만 위의 방식으로 숫자를 주는 절차를 끝낸 뒤에 한번에 인구를 분배하려면 또 맵 전체를 탐색해야한다.
       그래서 좀더 효율적인 방법이 없는지 생각해보았다.
   • 2nd 접근 - 영역별로 방문여부만 매기면서 BFS 탐색을 부분에 대해 돌린 후에 바로 인구를 분배 )
     • 두번째 접근은 첫번째와 달리 영역을 발견할때마다 바로 연산해서 인구를 분배하는 방식이다.
     • 공간을 크게 잡아먹지 않아도 되고, 1번에 비해 구현도 간단할것같아 이 방식을 선택했다.
4. 위 계획을 검증
   • 두 경우 전부 완탐이라 답을 찾을수밖에 없다. 
     완탐이 아닌 방식으로는 풀수가 없어 보인다..
5. 계획 수행 (실제코드 작성)
   1. Java 11

      1. import java.io.*;
         import java.util.*;
         
         public class Main {
             static int N,L,R,sum=0,days=0;
             static boolean isMove = false;
             static final int[] dx = {0,0,1,-1}, dy = {1,-1,0,0};
             static List<Point> union = new ArrayList<>();
             static boolean[][] vis;
             static int[][] map;
         
             public static void main(String[] args) throws IOException{
                 //System.setIn(new FileInputStream("src/input.txt"));
                 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());
                     }
                 }
         
                 // 1 loop = 1 days
                 while(true) {
                     isMove = false;
                     vis = new boolean[N][N];
         
                     for(int i=0; i<N; i++) {
                         for(int j=0;j<N; j++) {
                             if(!vis[i][j]){
                                 BFS(i,j);
                             }
                         }
                     }
                     // 위 완탐동안 진행한 곳이 없다면 break
                     if(!isMove) break;
                     else days++;
                 }
                 System.out.println(days);
             }
         
             static void BFS(int x, int y) {
                 Queue<Point> q = new LinkedList<>();
                 q.add(new Point(x,y));
                 vis[x][y] = true;
                 union.add(new Point(x,y));
         
                 while(!q.isEmpty()) {
                     Point node = q.poll();
         
                     for(int k=0; k<4; k++) {
                         int nx = node.x + dx[k];
                         int ny = node.y + dy[k];
         
                         if(0<=nx && nx<N && 0<=ny && ny<N && !vis[nx][ny]) {
                             if(L <= Math.abs(map[node.x][node.y] - map[nx][ny]) &&  Math.abs(map[node.x][node.y] - map[nx][ny]) <= R) {
                                 isMove = true;
                                 vis[nx][ny] = true;
                                 q.add(new Point(nx,ny));
                                 // 영역 더하기 위함
                                 union.add(new Point(nx,ny));
                             }
                         }
                     }
                 }
         
                 sum=0;
                 for (Point p : union) {
                     sum += map[p.x][p.y];
                 }
         
                 for(int i=0; i<union.size(); i++) {
                     Point p = union.get(i);
                     map[p.x][p.y] = sum / union.size();
                 }
                 union = new ArrayList<>();
             }
         }
         
         class Point{
             int x;
             int y;
         
             public Point(int x, int y) {
                 this.x = x;
                 this.y = y;
             }
         
             @Override
             public String toString() {
                 return "Point{" +
                         "x=" + x +
                         ", y=" + y +
                         '}';
             }
         }

 

• 결과 - sum을 초기화하는 부분을 잊어서 틀렸었다...허무해