[JAVA66] 16234. 인구이동

16234. 인구이동 (G4)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	75602	32262	18928	39.406 %

 

문제

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번 보다 작거나 같은 입력만 주어진다.

 

출력

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

---

summary

인구 이동이 발생한 일자 계산

• 조건(L이상 R이하) 에 해당하는 나라는 연합을 이루고 있음
• 연합을 이룬 나라사이에 인구이동이 발생
• 연합을 이루지 못할 때까지 반복함

 

strategy

시뮬레이션 + 완전탐색 (BFS)

• 나라별 인구 정보를 저장 (int[][] board)
• 방문 여부 체크, 매 날짜마다 초기화 (boolean[][] visited)
• 모든 나라별로 BFS 를 실행 단, 방문 기록이 없는 나라만 허용
• 나라 간에 인구차이가 L 이상 R이하면 연합을 이룸 (Queue<Point> group)
• 인구합(people), 국가수 (cnt), 국가좌표(group) 을 활용해서 인구 이동을 실행 (void move)
• 연합을 한번이라도 이루면 다음 날도 진행 (flag = true)

 

note

• 1 ≤ N ≤ 50
• 1 ≤ L ≤ R ≤ 100
• 0 ≤ A[r][c] ≤ 100
• 인구 이동이 발생하는 일수가 2,000번 보다 작거나 같음

 

import java.util.*;
import java.io.*;
import java.awt.Point;

public class Main {
    static int answer;
    static int N, R, L;
    static int[][] board;
    static int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static boolean[][] visited;
    static Queue<Point> group = new ArrayDeque<>();
    static boolean flag = false;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // input
        StringTokenizer input = new StringTokenizer(br.readLine());
        N = Integer.parseInt(input.nextToken());
        L = Integer.parseInt(input.nextToken());
        R = Integer.parseInt(input.nextToken());

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

        while(true) {
            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(flag) answer++; // 연합 존재
            else break;
        }

        System.out.println(answer);
    }

    public static void BFS(int x, int y) {
        Queue<Point> q = new ArrayDeque<>();
        q.add(new Point(x, y));
        visited[x][y] = true;
        
        group.clear(); 
        group.add(new Point(x, y)); // 연합 나라 저장 
    
        int people = board[x][y]; // 인구합
        int cnt = 1; // 연합 나라 수
        while(!q.isEmpty()) {
            Point current = q.poll();
            for(int[] d : dir) {
                int mx = current.x + d[0];
                int my = current.y + d[1];

                if(mx < 0 || my < 0 || mx >= N || my >= N) continue; // 범위 벗어남

                int diff = Math.abs(board[current.x][current.y] - board[mx][my]);
                if(diff < L || diff > R) continue; // 인구 수 차가 범위 벗어남
                if(visited[mx][my]) continue; // 방문여부 확인

                visited[mx][my] = true; // 방문
                q.add(new Point(mx, my));
                
                group.add(new Point(mx, my)); 
                cnt++;
                people += board[mx][my];
            }
        }

        if(cnt > 1) { // 연합 나라가 1개 초과
            flag = true; // 연합 구성
            move(people / cnt); // 인구 이동
        }
    }

    public static void move(int num) {
        while(!group.isEmpty()) {
            Point nation = group.poll();

            board[nation.x][nation.y] = num;
        }
    }
}

 

문제	결과	메모리	시간	언어코드	길이
16234	맞았습니다!!	298872 KB	592 ms	Java 11 / 수정	2688 B

memo

• group 을 전역으로 사용하면서 clear 잘못된 위치에서 하는 바람에 에러 발생