[백준] 16234번 인구이동(java)

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

16234번: 인구 이동

bfs를 사용하는 구현문제이다.

 

핵심

이 문제는 어떤 식으로 접근할지 충분히 생각하고 시작하면 쉽게 풀 수 있다.

우선 나는 각각 자리마다 bfs를 하여 이동한 곳을 모두 체크하고, 이후에 체크를 하지 않은 곳을 탐색하는 방법을 사용하였다.

또한 한 번에 bfs로 이동한 곳은 좌표를 담아서 changeMap을 통해 자리의 값을 바꿔주었다.

 

정답 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        L = sc.nextInt();
        R = sc.nextInt();

        map = new int[N][N];
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        int result = 0;

        while (true) {
            int switchingCount = 0;
            visited = new boolean[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visited[i][j]) {
                        switchingCount++;
                        bfs(i, j);
                    }
                }
            }
            if (switchingCount == N * N) {
                break;
            }
            result++;
        }
        System.out.println(result);
    }

    private static void bfs(int y, int x) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{y, x});
        visited[y][x] = true;
        int sum = map[y][x];
        List<int[]> change = new ArrayList<>();
        change.add(new int[]{y, x});

        while (!q.isEmpty()) {
            int[] move = q.poll();
            for (int i = 0; i < 4; i++) {
                int moveY = move[0] + dy[i];
                int moveX = move[1] + dx[i];

                if (validation(moveY, moveX)) {
                    continue;
                }
                int gap = Math.abs(map[moveY][moveX] - map[move[0]][move[1]]);
                if (!visited[moveY][moveX] && L <= gap && gap <= R) {
                    visited[moveY][moveX] = true;
                    change.add(new int[]{moveY, moveX});
                    q.offer(new int[]{moveY, moveX});
                    sum += map[moveY][moveX];
                }
            }
        }
        changeMap(change, sum);
    }

    private static boolean validation(int moveY, int moveX) {
        return !(0 <= moveY && moveY < N && 0 <= moveX && moveX < N);
    }

    private static void changeMap(List<int[]> list, int sum) {
        int changeValue = sum / list.size();
        for (int[] l : list) {
            map[l[0]][l[1]] = changeValue;
        }
    }
}

해설

한 번에 풀다 보니 다소 빡코딩이 되어버렸다. 

이 문제에서는 접근방법이 중요하기 때문에 이를 위주로 설명하겠다.

우선 인접한 맵의 크기가 L과 R사이라면 국경을 열 수 있다. 따라서 국경이 언제 열리지 않는지가 중요하다.

나는 switchingCount를 사용하여 국경이 열리는지를 판단하였다. 이는 bfs에서 다른 점으로 이동할 수 있다면 1곳이라도

열린 것을 의미한다. 따라서 N^2번 bfs가 돌아가면 국경이 열리지 않은 것이다.

이후 bfs로직에서 일반 bfs와 다른 점은 List에 이동한 좌표를 담아주었다.

이후 값을 변경하기 위함이다. 물론 이 방법 말고도 다른 방법이 존재하겠지만, 

리스트를 사용하여 간단하게 풀었다.

나머지 로직의 경우 쉽게 이해할 수 있을 것이다.

 

 

배운 점

이 문제는 처음에는 어려워 보였으나, 문제를 깊게 이해하고 어떤 식으로 풀지 로직을 천천히 구상하고 시작하니까

쉽게 풀 수 있었다. 이러한 구현 문제의 경우 초반 설계 및 접근 방법이 중요한 것 같다.

문제를 풀기 전에 충분히 생각하자.