인구 이동

면접 대비

시간 제한2초메모리 제한512 MB

요약

인구 차가 L 이상 R 이하인 국경을 열어 연결된 연합을 찾고 각 칸의 인구를 소수점을 버린 평균으로 바꿉니다. 변화가 없을 때까지 반복한 일수를 출력합니다.

난이도: 보통10점 중 5점
유형: 시뮬레이션, BFS, 유니온 파인드, 그래프
정답자: 아직 제출이 없습니다

문제

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

오늘부터 인구 이동이 시작된다.

인구 이동은 하루 동안 다음과 같이 진행되며, 아래 방법으로 인구 이동이 더 이상 일어나지 않을 때까지 계속된다.

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

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

입력

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

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

인구 이동이 발생하는 일수가 2,000 이하인 입력만 주어진다.

출력

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

예제5

예제 1
입력
```
2 20 50
50 30
20 40
```
예상 출력
```
1
```
예제 2
입력
```
2 40 50
50 30
20 40
```
예상 출력
```
0
```
예제 3
입력
```
2 20 50
50 30
30 40
```
예상 출력
```
1
```
예제 4
입력
```
3 5 10
10 15 20
20 30 25
40 22 10
```
예상 출력
```
2
```

예제 5

입력

4 10 50
10 100 20 90
80 100 60 70
70 20 30 40
50 20 100 10

예상 출력