문제 바로가기

나의 풀이

문제를 읽으면서 구현 문제인지는 파악했고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다 이 구문에서 끝날 때까지 반복되는 것을 구현해야하는 구나.. 그냥 브루트포스로 풀어야겠다고 생각했습니다.

처음에는 실제로 국경선과 일치하는 boolean[][] 배열을 생성해서 bfs를 돌리면서 국경선을 여닫은 후, 열린 국경선끼리는 또 인구 이동이 발생하는 식으로 구현을 해야하는가 생각했지만 비효율적이라 다른 방식을 생각해냈습니다.

bfs 메소드 내에서 이중 for문을 돌리며 모든 국가를 방문했는지 여부를 파악한 다음, 방문하지 않은 국가에 대해서 bfs를 시작하는데, 그 조건은 1) 이전에 방문하지 않은 나라 2) 인구수 차이가 범위 내인 나라 3) map 범위 내에 존재하는 나라 등이었습니다.

count 변수를 return 해줌으로써 실제로 인구이동이 몇번 일어났는지 파악해서 main 함수 내 while 문을 break 할 수 있도록 했습니다.

자세한 설명은 코드의 주석을 참고하시면 됩니다.

나의 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {

    static int n, l, r;
    static int[][] map;
    static boolean[][] visited;
    static int dx[] = {0, 0, -1, 1}, dy[] = {1, -1, 0, 0};

    static class Point {
        int x;
        int y;

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

    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());
            }
        }

        int answer = 0;
        while (true) {
            int ret = bfs();
            if (ret == 0) break;
            answer++;
        }

        System.out.println(answer);
    }

    public static int bfs() {
        Queue<Point> q = new LinkedList<>();
        visited = new boolean[n][n];
        int count = 0;
        // 모든 국가 탐색
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 이미 방문한 곳이면 스킵
                if (visited[i][j]) continue;

                // 방문 안한 국가면 bfs 시작
                q.offer(new Point(i, j));
                visited[i][j] = true;

                // 서로 국경 열리는 국가들 임시 저장해둘 list
                List<Point> list = new ArrayList<>();
                list.add(new Point(i, j));

                // 서로 국경 열리는 국가들 인구수 더해갈 변수
                int sum = map[i][j];

                // 이어진 국가들 죄다 q에 넣고 bfs
                while (!q.isEmpty()) {
                    Point cur = q.poll();
                    for (int k = 0; k < 4; k++) {
                        int nx = cur.x + dx[k];
                        int ny = cur.y + dy[k];
                        if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                        if (visited[nx][ny]) continue;

                        // next 국가와 cur 국가 간의 인구수 차이
                        int difference = Math.abs(map[nx][ny] - map[cur.x][cur.y]);
                        // 인구수 차이가 범위 안일때만 성공
                        if (l <= difference && difference <= r) {
                            visited[nx][ny] = true;
                            q.offer(new Point(nx, ny));
                            list.add(new Point(nx, ny));
                            sum += map[nx][ny];
                            count++;
                        }
                    }
                }

                // 이어진 국가들 간에 평균 인구수로 값 수정
                int population = sum / list.size();
                for (Point point : list) {
                    map[point.x][point.y] = population;
                }
            }
        }
        return count;
    }
}