[BOJ 16234] 인구이동 - JAVA

인구이동 구현방법에 대해 설명을 하겠습니다.

이 방법은 개인적인 방법이며 최적의 솔루션이 아닐 수 있습니다.

 

우선, 문제를 먼저 보면

 

문제설명

1. 국경선을 공유하는 나라 즉, 상하좌우에 있는 나라와 인구 수의 차이가 L명 이상 R명 이하로 난다면 두 나라는 국경선을 연다.

2. 국경선을 열 수 있는 나라가 모두 열리면 인구이동을 시작한다.

3. 인구이동이 시작되면 연합을 이룬 나라의 인구 수는 (연합의 인구 수) / (연합을 이루고 있는 칸의 개수) , 소수점 이하는 버림.

4. 이후 연합을 해체하고 모든 국경선을 닫는다.(연합을 이뤘던 각 나라의 인구 수는 (연합의 인구 수) / (연합을 이루고 있는 칸의 개수)로 유지)

5. 더이상 인구이동을 할 수 없을 때까지의 일 수를 구해야한다.

 

 

구현방법

가장 깊게 생각했던 부분 (개인적)

★ BFS 함수를 시작하는 첫 좌표의 국경선 여는 나라의 LIST에 포함하는 방법

-> 해결방법 : check 변수 사용

★ 하루에 두 곳 이상에서 한 번에 인구이동이 일어났을 때 해결방법

-> 해결방법1 : bfs함수 종료 직후 국경선이 열렸는지 확인 후 인구이동한 후 다음 방문 안한 나라 bfs함수 실행

-> 해결방법2 : temp 변수를 이용한 while문 종료조건

 

자세한 구현 방법은 코드 주석을 통해 설명드리도록 하겠습니다.

import java.util.*;
import java.io.*;
class Node{
    int x,y;
    Node(int x, int y){
        this.x = x;
        this.y = y;
    }
    int getX() {
        return x;
    }
    int getY() {
        return y;
    }
}
public class Main{
    static int n;
    static int l, r;
    static int[][] graph;    //인구수가 나와있는 배열
    static boolean[][] visited;    //방문한 곳 체크하는 배열
    static int[] dx = {0,0,-1,1};
    static int[] dy = {-1,1,0,0};
    static ArrayList<Node> move = new ArrayList<>();    //인구이동이 일어나는 좌표 저장
    static int result;    //인구이동이 일어나는 곳 인구 수 합
    static void bfs(int x, int y) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x, y));
        visited[x][y] = true;
        boolean check = false;
        /*
         * check는 맨 처음 좌표를 제크하고
         * 비교 후 인구이동이 일어나는 곳이면
         * 리스트에 포함하기 위해 사용하는 변수
         */
        
        while(!q.isEmpty()) {
            int k = q.size();
            for(int i=0;i<k;i++) {
                Node node = q.poll();
                x = node.getX();
                y = node.getY();
                for(int j=0;j<4;j++) {
                    int nx = x+dx[j];
                    int ny = y+dy[j];
                    if(nx>=n||ny>=n||nx<0||ny<0)
                        continue;
                    if(visited[nx][ny])
                        continue;
                    
                    /*
                     * graph배열 내 좌표이고 방문하지 않았으며,
                     * x,y좌표와 nx,ny 좌표 차이의 절대값이ㅣ이상,
                     * r이하이면 국경선이 열린다.
                     */
                    if(Math.abs(graph[nx][ny]-graph[x][y])>=l&&Math.abs(graph[nx][ny]-graph[x][y])<=r) {
                        q.offer(new Node(nx,ny));
                        visited[nx][ny] = true;
                        
                        /* 
                         * check는 위에서 말했듯이 함수의 맨 처음 좌표가
                         * 인구이동을 하는 나라에 포함이 된다면
                         * check를 true하여 다음 좌표들은 조건이 성립하지 않도록한다.
                         */
                        if(!check) {
                            result += graph[x][y];
                            move.add(new Node(x, y));
                            check = true;
                        }
                        
                        /*
                         * 인구이동을 하는 나라에 포함이 된다면
                         * result에 인구 값을 더하고
                         * 국경선 여는 나라 list에 포함 시킨다.
                         */
                        result += graph[nx][ny];
                        move.add(new Node(nx, ny));
                    }
                }
            }
        }
    }
   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 stok = new StringTokenizer(br.readLine());
      n = Integer.parseInt(stok.nextToken());
      l = Integer.parseInt(stok.nextToken());
      r = Integer.parseInt(stok.nextToken());
      graph = new int[n][n];
      visited = new boolean[n][n];
      for(int i=0;i<n;i++) {
          stok = new StringTokenizer(br.readLine());
          for(int j=0;j<n;j++) {
              graph[i][j] = Integer.parseInt(stok.nextToken());
          }
      }
      int cnt = 0;
      result = 0;
      move = new ArrayList<>();
      
      while(true) {
          visited = new boolean[n][n];//하루가 지날때마다 방문 배열은 초기화한다.
          int temp = 0;    //while문 종료조건
          for(int i=0;i<n;i++) {
              for(int j=0;j<n;j++) {
                  if(!visited[i][j]) {
                      bfs(i,j);
                      if(result>0) {//bfs함수를 통해 국경선을 여는 나라가 있으면
                          int k = move.size();
                          for(Node node:move) {//국경선을 여는 나라들 평균값을 넣어준다(소수점 이하 버림)
                              graph[node.getX()][node.getY()] = result/k;
                          }
                          //초기화
                          result = 0;
                          move = new ArrayList<>();
                          temp++;
                      }
                  }
              }
          }
          if(temp==0)    //그래프 전체를 탐색해도 국경선을 여는 나라가 없으면 while문 종료
              break;
          cnt++;    //하루씩 증가
      }
      bw.write(String.valueOf(cnt));
      bw.flush();
   }
}

 

구현을 마무리하고 보니 고민했던 부분은 아무것도 아닌것처럼 보였다,, 저것들 때문에 1시간이나 고민했는데,,,

아직 경험이 많이 부족해서 그런거라고 생각하고 열심히 코테준비를 해야겠다 !!!