인구 이동

💻 입력 조건

• 첫째 줄에 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

💻 입력 예시2

2 40 50 
50 30
20 40

💻 출력 예시2

0

💻 입력 예시3

2 20 50
50 30
30 40

💻 출력 예시3

1

💻 입력 예시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

📖 문제 해결
bfs 함수를 이용하여 인접한 나라들부터 차근차근 인구수의 차이를 확인하며 연합이 되는지 안 되는지에 대해 결정하고, 연합인 나라들끼리는 균일한 인구수를 가질 수 있도록 코드를 작성하였습니다.
그리고 연합 국가의 개수(u_count)와 나라의 개수(n*n)가 같지 않은 상태일 때만 인구 이동을 진행하고, 연합 국가의 개수와 나라의 개수가 같은 상태인 경우 인구 이동을 멈추고 총 실행한 인구 이동의 횟수를 출력합니다.

# n, l, r 입력받기
n, l, r = list(map(int,input().split()))

# 인구수 정보 입력받기
population = []

for i in range(n):
    population.append(list(map(int,input().split())))

# 연합 국가 표시 리스트
union = [[-1]*n for i in range(n)]

from collections import deque

queue = deque()

# 상, 하, 좌, 우를 살펴보기 위함
dx = [-1, +1, 0, 0]
dy = [0, 0, -1, +1]

def bfs(r_,c_,u_count):
    
    count = 0
    sum_ = 0
    coordi = []
    
    queue.append((r_,c_))
    count += 1
    sum_ += population[r_][c_]
    coordi.append((r_,c_))
    
    union[r_][c_] = u_count
    
    # queue를 이용하여 연합이 될 수 있는 국가들을 모두 찾을 때까지 진행
    while queue:

        r_idx, c_idx = queue.popleft()

        for i in range(4):
            r_range = 0 <= r_idx + dx[i] and r_idx + dx[i] <= n-1
            c_range = 0 <= c_idx + dy[i] and c_idx + dy[i] <= n-1

            if r_range and c_range:
                sub = abs(population[r_idx][c_idx] - population[r_idx + dx[i]][c_idx + dy[i]])

                # 두 국가 간의 인구 수 차이가 주어진 범위 내라면
                # 두 국가를 연합 국가로 지정
                if l <= sub and sub <= r and union[r_idx + dx[i]][c_idx + dy[i]] == -1:   
                    union[r_idx + dx[i]][c_idx + dy[i]] = u_count
                    queue.append((r_idx + dx[i],c_idx + dy[i]))
                    count += 1
                    sum_ += population[r_idx + dx[i]][c_idx + dy[i]]
                    coordi.append((r_idx + dx[i],c_idx + dy[i]))
    
    # 만들어진 연합 국가들에 대하여 인구를 고르게 분포시킴
    avg_population = int(sum_/count)
    
    for r_idx, c_idx in coordi:
        population[r_idx][c_idx] = avg_population

# 인구 이동이 몇 번 일어났는지 저장해두는 변수
result_count = 0

while True:
    
    union = [[-1]*n for i in range(n)]
    
    # 연합 국가의 개수를 세는 변수
    u_count = 0

    for r_, row in enumerate(population):
        for c_, col in enumerate(row):
            
            # 연합 국가의 가능성 조사를 하지 않은 국가에 대하여 조사
            if union[r_][c_] == -1:
                bfs(r_,c_,u_count)
                u_count += 1
    
    # 만약 연합 국가의 개수 = 나라의 개수 라면 
    # 인구 이동이 더 이상 일어나지 않는다는 의미이므로 반복문 실행을 멈춤
    if u_count == n*n:
        break
    
    result_count += 1

print(result_count)