16234-백준-인구이동

1. 문제 출처

https://www.acmicpc.net/problem/16234

16234번: 인구 이동

2. 풀이

연구소 문제와 비슷한 점이 있다. 연합하고 인구를 이동 시켜주는 작업을 BFS를 사용하여 구현하고 연합체의 개수가 전체 데이터의 수와 같으면 반복 했던 횟수를 반환한다...

from collections import deque

# 입력
N,L,R = map(int, input().split())
A = []
for _ in range(N):
    A.append(list(map(int,input().split())))


# 상하좌우 확인
dx = [0,0,-1,1]
dy = [-1,1,0,0]


    
# 연합 해주기 (BFS)
def make_ally(start,union,ally_num): 
    # 큐
    queue = deque([start])
    # 연합 맴버
    ally = [start]
    # 연합 인구수 총합
    ally_sum = A[start[0]][start[1]]
    # 연합 나라 수
    ally_count = 1
    # 해당 나라를 ally_num번째 연합으로 한다.
    union[start[0]][start[1]] = ally_num
    while queue:
        r,c = queue.popleft()
        # 상하좌우확인
        for idx in range(4):
            x = r+dx[idx]
            y = c+dy[idx]
            if (0<=x<N) and (0<=y<N):
                # 만약 연합을 가입하지 않았고 인구 차이가 L,R 사이이면 연합한다
                if (union[x][y] == -1) and( L<=abs(A[r][c] - A[x][y])<=R):
                    ally_sum += A[x][y]
                    union[x][y] = ally_num
                    ally.append([x,y])
                    ally_count += 1
                    queue.append([x,y])
    # 연합했던 나라의 인구를 평균으로 맞춘다.          
    for i,j in ally:
        A[i][j] = int(ally_sum/ally_count)
                
            

    
    
def move_count():
    # 총 이동에 걸린 날
    count = 0
    # 이동이 종료될 때 까지 반복
    while True:
        # 연합 정보
        union = [[-1] * N for _ in range(N)]
        # 연합 번호
        ally_num = 0
        for i in range(N):
            for j in range(N):
                # 만약 연합 하지 않았다면 
                if union[i][j]==-1:
                    # 연합 작업 실시
                    make_ally([i,j],union,ally_num)
                    ally_num+=1
        # 만약 연합의 개수가 나라의 개수와 같으면 종료
        if ally_num == N*N:
            print(count)
            break
        count+=1
    
move_count()