백준 16234번 인구이동(자바) - bfs

인구 이동 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

44448

17476

10033

35.982%

문제

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

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

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

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

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

입력

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력

인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.

예제 입력 1 복사

2 20 50
50 30
20 40

예제 출력 1 복사

1

초기 상태는 아래와 같다.

L = 20, R = 50 이기 때문에, 모든 나라 사이의 국경선이 열린다. (열린 국경선은 점선으로 표시)

연합은 하나 존재하고, 연합의 인구는 (50 + 30 + 20 + 40) 이다. 연합의 크기가 4이기 때문에, 각 칸의 인구수는 140/4 = 35명이 되어야 한다. 

예제 입력 2 복사

2 40 50
50 30
20 40

예제 출력 2 복사

0

---

- list를 만들어서 bfs를 한 번 진행했을때 연합되는 모든 칸들의 인덱스를 저장한다.

- people 변수를 만들어서 연합된 국가의 인구 수를 모두 더한다.

- 한 번의 bfs 실행이 끝나면 list 안에 연합된 국가들이 들어있으므로 list의 size가 1보다 큰 경우 각각의 map[i][j] 값을 people/list.size() 값으로 변경해준다.

- 그 후 flag를 true로 바꿔 연합되는 국가가 있음을 표시한다.

만약 모든 칸을 다 돌아도 연합되는 국가가 없으면 flag 값은 false를 갖게되므로 실행을 종료하고 답을 출력한다.

import java.util.*;

class Node {
    int x;
    int y;
    Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
public class Main {
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int n,l,r;
    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();
            }
        }

        boolean flag;
        int day = 0;
        do {
            flag = false; //처음 flag 값은 false로
            visited = new boolean[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (!visited[i][j]) {
                        bfs(i,j);
                        if (list.size() > 1) {  //연합되는 국가가 있는 경우
                            for (int k = 0; k < list.size(); k++) {
                                map[list.get(k).x][list.get(k).y] =
                                        people / list.size();
                            }
                            flag = true;  //만약 연합되는 국가가 있으면 true로 변경
                        }
                    }
                }
            }
            if (flag) day++;  //연합되는 국가 있는 경우 일 수를 증가
        } while (flag); //연합되는 국가가 없어질 때까지 진행

        System.out.println(day);

    }

    static int people;
    static List<Node> list;
    static void bfs(int i, int j) {
        list = new ArrayList<>();  //연합되는 국가의 인덱스를 저장하기 위한 리스트
        people = 0;
        Queue<Node> que = new LinkedList<>();
        que.offer(new Node(i, j));
        visited[i][j] = true;
        people += map[i][j];  //연합 국가들의 인구수를 모두 더해 저장하는 변수
        list.add(new Node(i,j));
        while (!que.isEmpty()) {
            Node now = que.poll();
            for (int k = 0; k < 4; k++) {
                int x = now.x + dx[k];
                int y = now.y + dy[k];
                if (x >= n || y >= n || x < 0 || y < 0) {
                    continue;
                }
                int gap = Math.abs(map[now.x][now.y] - map[x][y]);
                if (!visited[x][y] && gap >= l && gap <= r) {
                    que.offer(new Node(x,y));
                    visited[x][y] = true;
                    people += map[x][y];
                    list.add(new Node(x,y));
                }
            }
        }
    }
}