문제
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경계를 공유하는 나라의 인구 차이가 모두 L보다 작아서 인구 이동이 발생하지 않는다.
예제 입력 3
2 20 50
50 30
30 40예제 출력 3
1초기 상태는 아래와 같다.
L = 20, R = 50이기 때문에, 아래와 같이 국경선이 열린다.
인구 수는 합쳐져있는 연합의 인구수는 (50+30+30) / 3 = 36 (소수점 버림)이 되어야 한다.
예제 입력 4
3 5 10
10 15 20
20 30 25
40 22 10예제 출력 4
2예제 입력 5
4 10 50
10 100 20 90
80 100 60 70
70 20 30 40
50 20 100 10예제 출력 5
3문제 풀이
import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class BJ16234 {
static int N,L,R,cnt;
static int[][] map;
static int[][] visited;
static int[][] moves={{0,1},{1,0},{0,-1},{-1,0}};
static int day;
static boolean flag;
static int[][] copy;
static int n,sum;
static int pop_count;
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];
copy=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) {
cnt=0;
//연합 표시해주기
visited = new int[N][N];
flag=false;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (visited[i][j] == 0) {
cnt++;
bfs(i, j);
if(n>1){
move();
flag=true;
}
}
}
}
if(!flag){
System.out.println(day);
System.exit(0);
}
day++;
}
}
private static void move() {
int pop=sum/n;
//인구이동하기
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(visited[i][j]==cnt){
map[i][j]=pop;
}
}
}
}
private static void bfs(int i,int j) {
n=1;
sum=map[i][j];
Queue<Point> queue=new ArrayDeque<>();
queue.offer(new Point(i,j));
while(!queue.isEmpty()){
Point p=queue.poll();
visited[p.x][p.y]=cnt;
for(int d=0;d<4;d++){
int a=p.x+moves[d][0];
int b=p.y+moves[d][1];
if(a<0 || a>=N || b<0 || b>=N) continue;
int tmp=Math.abs(map[a][b]-map[p.x][p.y]);
if(visited[a][b]==0 && tmp>=L && tmp<=R){
queue.offer(new Point(a,b));
visited[a][b]=cnt;
n++;
sum+=map[a][b];
}
}
}
}
}이 문제를 해결하기 위해선 다음과 같은 로직을 생각해야한다.
- 인접 지역끼리의 인구차이를 계산하고
- 조건이 맞다면 경계를 개방하기
- 연합 지역들끼리 인구수를 모두 합치고 평균값을 갱신해주기
- 인구이동이 더이상 일어나지 않을때까지 반복하기
인구 이동 시작 전
while(true) {
cnt=0;
//연합 표시해주기
visited = new int[N][N];
flag=false;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (visited[i][j] == 0) {
cnt++;
bfs(i, j);
if(n>1){
move();
flag=true;
}
}
}
}
if(!flag){
System.out.println(day);
System.exit(0);
}
day++;
}더이상 인구이동이 일어나지 않을때까지 탐색을 반복해야하기 때문에 while문을 반복해준다.
cnt는 해당 연합 번호를 나타내기 위해서 선언한 변수로 같은 연합이면 같은 번호를 나타내고
방문 표시를 위해 하루치의 인구이동이 일어날때마다 visited를 초기화해준다.
map을 하나씩 탐색하여 방문하지 않은 지역이라면 새로운 연합 번호를 생성하고 인접한 지역들을 모두 탐색하여 같은 연합인 지역들을 찾는다.
이때, 연합 지역의 개수가 1개 이상이라면 인구이동이 일어난다고 판단하고 flag를 true로 설정한다.
이 과정을 반복할때마다 하루가 흘러가기 때문에 day값이 다음날로 넘어간다.
모든 지역 탐색이 끝났음에도 불구하고 flag값이 false라면 인구이동이 일어나지 않았다는 뜻이기 때문에 답을 출력해준다.
bfs 탐색
인근 지역끼리 경계를 개방할 수 있는지, 개방할 수 있다면 연합지역으로 묶기 위해 bfs 탐색을 이용한다.
그래프라고 생각하면 각 노드끼리 이어지는지 조건을 확인하는 것이다.
private static void bfs(int i,int j) {
n=1;
sum=map[i][j];
Queue<Point> queue=new ArrayDeque<>();
queue.offer(new Point(i,j));
while(!queue.isEmpty()){
Point p=queue.poll();
visited[p.x][p.y]=cnt;
for(int d=0;d<4;d++){
int a=p.x+moves[d][0];
int b=p.y+moves[d][1];
if(a<0 || a>=N || b<0 || b>=N) continue;
int tmp=Math.abs(map[a][b]-map[p.x][p.y]);
if(visited[a][b]==0 && tmp>=L && tmp<=R){
queue.offer(new Point(a,b));
visited[a][b]=cnt;
n++;
sum+=map[a][b];
}
}
}
}n은 각 연합의 지역 개수를 나타내고, sum은 연합의 인구 총합이다.
각 지역에서 상하좌우로 인접한 지역을 모두 탐색하여 인구수의 차이가 L<= 인구수 차이 <= R이라면 큐에 해당 지역 좌표를 넣어주고 방문 처리를 해준뒤 평균값 계산을 위해 연합 지역 수를 증가, 해당 지역의 인구수를 합계에 더해준다.
방문처리를 할때에는 boolean값이 아니라 해당 지역의 연합 번호인 cnt값을 넣어준다.
이 과정을 반복하면 같은 연합인 지역들을 모두 탐색할 수 있게된다.
인구 이동
private static void move() {
int pop=sum/n;
//인구이동하기
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(visited[i][j]==cnt){
map[i][j]=pop;
}
}
}
}bfs 탐색을 통해 한 연합의 지역들을 모두 찾아냈다면 인구이동을 해야한다.
해당 지역들의 인구수 평균을 구하고 방문 배열의 값이 인구를 이동하고자 하는 연합의 번호와 같다면 해당 지역은 이동하려는 연합에 속해있으므로 값을 갱신해준다.
메인 코드에서 if(n>1)인 경우에만 인구이동을 하고 flag값을 바꿔주도록 되어있는데
처음에 코드를 짰을때는 무조건 인구이동을 하도록 하고
인구 이동 메소드가 일어나기 전 map의 값과 인구 이동 메소드가 일어난 후 map의 값이 같다면 인구이동이 일어나지 않았다고 판단하여 답을 출력했다.
그러기 위해서는 이전 map의 값을 저장해야했기 때문에 깊은 복사를 위해 2중 for문을 또 쓰게 되었고 결국 시간초과를 발생했다.
if문 하나를 적용하고 for문을 줄이니 시간초과 없이 답을 제대로 출력할 수 있었다.
