[백준 16234] 인구 이동 / 자바 / bfs

#문제

레벨: G4
알고리즘: bfs
풀이시간: 50분
힌트 참조 유무:

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

---

#문제 풀이

특정 국가(A)를 기준점으로 삼고 그 국가와 연할될 수 있는 국가(B)를 찾고 B와 연합될 수 있는 국가를 찾고(C) 반복한다. 이 형식 어디서 보지 않았는가? 4방향+bfs(or dfs)이다. 그런데 bfs 한 번으로 모든 국가를 다 탐색할 수는 없다. 그래서 이중 for문으로 모든 국가를 돌대 visited =false(방문하지 않은) 곳만 bfs(or dfs)를 돌린다. 코드는 둘 다 첨부하겠다.

코드를 보면 bfs(or dfs)를 마치고나서 인구이동을 시킨다. bfs로 인접국가를 순회하는 김에 인구이동까지 하면 안되나? 라는 충동이 들었지만, 구현이 복잡하고 그게 가능한지도 모르겠다. 그래서 N이 50 이하라 미세한 차이겠지만, 성능을 포기하고 직관적인 코드를 위해서 bfs(or dfs)로 인접국가를 탐색한 후, 그 결과를 바탕으로 인구이동을 시켰다.

dfs 코드에서 인접국가의 결과를 어떻게 리턴할지 고민한 지점이 있다. 이 고민은 파라미터에 리스트를 넘김으로써 해결했다. dfs 순회 중 인접국가라면 리스트에 담는 것이다. 순회를 마쳤다면 리턴해주는 것이 아니라 그대로 void 형태로 끝내면된다. 그 이유는 리스트를 파라미터로 넘기면 call by value이지만, 호출당한 메소드(dfs)의 파라미터는 호출한 쪽의 리스트가 가르키는 배열을 똑같이 가르키고 있으므로(일명, 얕은 복사) 배열의 수정이 가능하기 때문입니다. 이로 인해 굳이 리턴을 안 해줘도 되는 것입니다.

---

#풀이 코드

bfs 코드

import java.util.*;
import java.io.*;

public class Main {
    static int N, L, R;
    static int[][] A;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {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());

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

        System.out.println(solution());
    }

    static int solution() {
        int days = 0;
        while (true) {
            visited = new boolean[N][N];
            boolean moved = false;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visited[i][j]) {
                        int population = bfs(i, j);
                        if (population > 1) moved = true;
                    }
                }
            }
            if (!moved) return days;
            days++;
        }
    }

    static int bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        List<int[]> united = new ArrayList<>();
        queue.offer(new int[]{x, y});
        united.add(new int[]{x, y});
        visited[x][y] = true;

        int total = A[x][y];
        int count = 1;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = current[0] + dx[i];
                int ny = current[1] + dy[i];

                if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny]) {
                    int diff = Math.abs(A[current[0]][current[1]] - A[nx][ny]);
                    if (diff >= L && diff <= R) {
                        queue.offer(new int[]{nx, ny});
                        united.add(new int[]{nx, ny});
                        visited[nx][ny] = true;
                        total += A[nx][ny];
                        count++;
                    }
                }
            }
        }

        int newPopulation = total / count;
        for (int[] pos : united) {
            A[pos[0]][pos[1]] = newPopulation;
        }

        return count;
    }
}

dfs코드

import java.io.*;
import java.util.*;

public class Main {
   static int N, L, R;
   static int[][] map;
   static boolean[][] visited;
   static int[] dx = {-1, 1, 0, 0};
   static int[] dy = {0, 0, -1, 1};
   static int days = 0;

   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];

       // 맵 입력 받기
       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];
           boolean moved = false;

           // 모든 좌표에 대해 연합 확인
           for(int i = 0; i < N; i++) {
               for(int j = 0; j < N; j++) {
                   if(!visited[i][j]) {
                       List<Point> union = new ArrayList<>();
                       dfs(i, j, union);

                       // 인구 이동 처리
                       if(union.size() > 1) {
                           int total = 0;
                           for(Point p : union) {
                               total += map[p.x][p.y];
                           }
                           int avg = total / union.size();
                           for(Point p : union) {
                               map[p.x][p.y] = avg;
                           }
                           moved = true;
                       }
                   }
               }
           }

           // 인구 이동이 없으면 종료
           if(!moved) break;
           days++;
       }

       System.out.println(days);
   }

   static void dfs(int x, int y, List<Point> union) {
       visited[x][y] = true;
       union.add(new Point(x, y));

       for(int i = 0; i < 4; i++) {
           int nx = x + dx[i];
           int ny = y + dy[i];

           if(nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny]) {
               int diff = Math.abs(map[x][y] - map[nx][ny]);
               if(diff >= L && diff <= R) {
                   dfs(nx, ny, union);
               }
           }
       }
   }

   static class Point {
       int x, y;

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