문제
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번 보다 작거나 같은 입력만 주어진다.
출력
인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.
구현코드
import java.io.*;
import java.util.*;
class Country{
private int x;
private int y;
public Country(int x, int y){
this.x = x;
this.y = y;
}
public int getX(){
return this.x;
}
public int getY(){
return this.y;
}
}
public class Main{
public static int n, min, max, groupCount = 0, time = 0;
public static int[][] arr;
public static boolean[][] visited;
public static int[] dx = {0, 0, -1, 1};
public static int[] dy = {-1, 1, 0, 0};
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());
min = Integer.parseInt(st.nextToken());
max = Integer.parseInt(st.nextToken());
arr = new int[n][n];
visited = new boolean[n][n];
for(int i = 0; i < n ; i++){
st = new StringTokenizer(br.readLine());
for(int j = 0; j < n; j++){
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
// 더이상 인구이동이 없을 때까지 반복
while(true){
for(int i = 0; i < n; i++){
for(int j = 0 ; j < n; j++){
// 방문여부 체크 후 실행
if(!visited[i][j]){
visited[i][j] = true;
int unionCount = bfs(i, j);
// 연합에 속한 국가가 1이상이면 인구이동을 한 연합 ++
if(unionCount > 1){
groupCount++;
}
}
}
}
// 인구이동을 한 연합의 개수가 0이면 인구이동이 일어나지 않은 것이기 때문에 반복문을 빠져나간다.
if(groupCount == 0){
break;
}
// 시간을 1초 추가
time++;
// 인구이동한 결과를 다시 인구이동 시켜야 하기 때문에 인구이동을 한 연합의 개수 0으로 초기화
groupCount = 0;
// 방문여부 초기화
for(int i = 0 ; i < n ;i++) {
Arrays.fill(visited[i], false);
}
}
System.out.println(time);
}
public static int bfs(int x, int y){
// bfs 를 반복시킬 queue
Queue<Country>queue = new LinkedList<>();
// 연합을 담을 list
ArrayList<Country>list = new ArrayList<>();
queue.offer(new Country(x, y));
list.add(new Country(x, y));
int unionCount = 1;
int sum = arr[x][y];
while(!queue.isEmpty()){
Country now = queue.poll();
for(int index = 0; index < 4 ; index ++){
int nx = now.getX() + dx[index];
int ny = now.getY() + dy[index];
// 범위체크와 , 방문여부 체크
if(0 <= nx && nx < n && 0 <= ny && ny < n && !visited[nx][ny]){
// 인구의 차이를 절대값으로
int sub = Math.abs(arr[now.getX()][now.getY()] - arr[nx][ny]);
// 인구차가 범위에 맞는지 비교
if(sub >= min && sub <= max){
queue.offer(new Country(nx, ny));
visited[nx][ny] = true;
list.add(new Country(nx, ny));
unionCount++;
sum += arr[nx][ny];
}
}
}
}
// sum을 평균 값으로 할당
sum /= list.size();
for(int i = 0; i < list.size(); i++){
// 연합의 지역들을 평균값으로 넣어주기
Country now = list.get(i);
arr[now.getX()][now.getY()] = sum;
}
// 연합에 속한 국가들을 return
return unionCount;
}
}
코드해석
이 문제는 BFS 를 사용해서 풀수있는 문제이다. 이 사실은 BFS 문제를 풀어본 사람들은 다 알것이다. 하지만 BFS 를 어떻게 사용해야 풀수있는문제일까 고민해보자.
- 문제에서 주어진 수를 보면 인구이동을 할수있는 범위가 주어진다. 국가들은
인접한 국가들의 인구와 자신의 국가의 인구수를 비교해서 차이가 범위의 값과
일치한다면 인구이동을 해주어야한다.
이 조건만 생각한다면, 우리는 배열의 범위만큼 반복문을 돌려서 BFS 를 진행시키고 구간들의 평균 값을 그 구간의 값에 넣어주면 된다. 하지만 이 문제에는 조건이 하나 더있다.
- 인구이동이 불가능 할때 까지 진행시키고 , 걸린 시간을 구해라 라는 것이다.
이 조건 때문에 우리는 전체구간에 BFSf를 진행시키는 것을 인구이동이 불가능 할 때 까지 반복시켜야한다.
그래서 코드를 구현시킬때 while 문 안에 모든 구간의 값에 BFS 를 진행했다.
그리고 만약에 인구이동이 없다면 반복문을 빠져나가도록 진행했다.
여기서 또 중요한 핵심은 방문여부 체크 배열을 초기화 시켜주는 것이다.
이 부분만 생각한다면 쉽게풀수있을 것이라 장담한다.
