[BOJ] 16234 인구이동 - JAVA

1. 문제

16234번: 인구 이동

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.

---

2. 풀이

static 변수 및 입력 받는 부분

static int N,L,R;
static int[][] area,next;
static boolean[][] visited;
public static void main(String[] args) throws IOException {
   BufferedReader in =new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer st = new StringTokenizer(in.readLine());
   N = Integer.parseInt(st.nextToken());
   L = Integer.parseInt(st.nextToken());
   R = Integer.parseInt(st.nextToken());

   area = new int[N][N];
   for(int i=0;i<N;i++){
      st = new StringTokenizer(in.readLine());
      for(int j=0;j<N;j++){
         area[i][j] = Integer.parseInt(st.nextToken());
      }
   }

 

BFS 함수를 호출하고 결과 출력하는 부분

• 바로 위의 코드와 이어진다. 
• result는 더 이상 인구이동을 해야하는지, cnt는 몇 번 인구이동을 했는지 저장하는 변수다. 마지막에 cnt를 출력한다.
• visited는 하루동안의 방문여부, next배열은 하루동안의 인구이동이 일어난 후의 결과배열이다. 주변 값에 영향을 줄 수 있기 때문에 area배열에 바로바로 인구이동 결과를 저장하지 않는다.

1. 인구이동이 하루 일어날 때마다 visited배열, next배열을 초기화한다. 날마다 방문할 수 있는 범위가 달라지고, 다음날의 인구이동결과를 저장하기 위해서다. result 변수도 while반복문에 들어온 뒤 false로 바꾼다.
2. [i][j]에 방문한 적 없다면 visited를 true로 표시하고 그 자리를 시작점 삼아 bfs함수를 호출한다.
3. bfs함수는 인구이동이 일어났는지, 일어나지 않았는지를 true/false로 구분해 반환한다.
4. 하루가 시작했을때의 result는 false이므로 한 번이라도 인구이동이 일어났다면 result는 마지막에 true가 될 것이다.
5. 그러면 다음 날도 인구이동 탐색을 시작한다.
6. 다음 날이 되기 전에 area에 현재 인구이동 결과를 저장한다. 
7. result가 true라면 오늘 인구이동이 일어난 것이므로 cnt+1을 한다. (굳이 이 조건문을 쓰지 않고 마지막 출력에 cnt-1을 해도 된다.)

   boolean result = true;
   int cnt = 0;
   while(result){
      result = false;
      visited = new boolean[N][N];
      next = new int[N][N];
      for(int i=0;i<N;i++){
         for(int j=0;j<N;j++){
            if(visited[i][j]) continue;
            visited[i][j] = true;

            result = result|bfs(new int[]{i,j});//이 부분
         }
      }
      area = next;
      if(result) cnt++;
   }

   System.out.println(cnt);
}

 

BFS

1. 초기값을 queue에 넣는다.
2. list는 인구이동이 일어나야할 위치를 저장하는 객체다. 마지막에 한꺼번에 인구이동해야하기 때문이다.
3. 큐가 빌 때까지 다음을 반복한다.
   1. 큐에서 값을 뽑는다.
   2. list에 그 값을 저장한다.
   3. 총 인구(total)에 현재 위치의 인구수를 더한다.
   4. 현재 위치에서 갈 수 있는 곳을 방문 처리 하고 큐에 더한다. 갈 수 있는 곳은 (현재인구수-다음위치인구수)가 L이상 R이하이고 방문한 적이 없는 곳이다.
4. 탐색이 끝났다면 (총 인구수 / 연합국가수)로 각 연합국가에 새로 저장될 인구 수를 구한다.
5. list에 저장된 위치에 접근해서 새 인구를 저장한다.
6. 만약 list의 크기가 1보다 크다면 초기국가 말고 다른 국가와 연합된 적 있는 것이므로 true, 1이라면 false를 반환한다.

private static boolean bfs(int[] pos) {
   int[][] deltas =  {{1,0},{-1,0},{0,1},{0,-1}};
   int total = 0;

   ArrayList<int[]> list = new ArrayList<>();
   Queue<int[]> queue = new ArrayDeque<>();
   queue.offer(pos);

   while(!queue.isEmpty()){
      pos = queue.poll();
      list.add(pos);

      int pop = area[pos[0]][pos[1]];
      total += pop;

      for(int d=0;d<4;d++){
         int ni = pos[0] + deltas[d][0];
         int nj = pos[1] + deltas[d][1];
         if(ni<0 || nj< 0 || ni>=N || nj>=N || visited[ni][nj]) continue;
         int diff = Math.abs(pop-area[ni][nj]);
         if(diff<L || diff>R) continue;
         visited[ni][nj] = true;
         queue.offer(new int[]{ni,nj});
      }
   }

   int div = total/list.size();
   for (int[] npos : list) {
      next[npos[0]][npos[1]] = div;
   }

   return list.size()!=1;
}

---

3. 결과

result를 갱신하는 부분에서 조금 헷갈려서 틀렸다. result를 true로 놓고 result=bfs(new int[]{i,j})로 값을 받았었는데 이렇게하면 마지막 값으로 갱신되어 내가 원하는 "하나라도 true이면 계속"할 수가 없다. 따라서 while문에 들어오면 바로 result를 false로 바꾸고 bfs를 부를때마다 그 값과 현재의 result값을 |연산했다.