백준 16234번: 인구 이동

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

16234번: 인구 이동

문제

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번 보다 작거나 같은 입력만 주어진다.

출력

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

---

"""
모든 땅에서 bfs를 수행한다
앞에서 bfs를 수행하면서 거쳤던 곳은 visited==1이 되게 해서
중복연산은 되지 않게 한다

모든 땅에서 bfs수행이 끝나면 날짜수를 +1해준다

이것을 계속 반복하고 bfs가 수행하면서 아무것도 하지않으면 중단
"""

from collections import deque
n,l,r=map(int,input().split()) #NxN크기의 땅, 인접한 나라의 인구차 L명이상 R명이하

graph=[] #땅에 있는 나라 정보
for i in range(n):
    graph.append(list(map(int,input().split())))


visited=[[0]*n for _ in range(n)] #방문표시할 리스트
dx=[1,-1,0,0]
dy=[0,0,1,-1]
def bfs(x,y):
    queue=deque()
    queue.append((x,y))
    visited[x][y]=1 #현재 칸 방문표시
    sum=graph[x][y] #인구 수를 더할 변수
    count=1 #나라 수를 셀 변수
    coor=[(x,y)] #연합 할 나라의 좌표들을 저장할 리스트
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx<0 or nx>=n or ny<0 or ny>=n:
                continue
            if (l<=(graph[x][y]-graph[nx][ny])<=r or l<=(graph[nx][ny]-graph[x][y])<=r) and visited[nx][ny]==0: #연합 가능한 나라일 때
                count+=1 #나라 수 카운트
                sum+=graph[nx][ny] #인구 수 더함
                coor.append((nx,ny))
                visited[nx][ny]=1 #방문표시
                queue.append((nx,ny))
    #bfs수행이 끝난 후
    if len(coor)==1: #연합 가능한 나라가 없을 때
        return -1
    p=sum//count #인구수=인구합/나라수
    for i in coor:
        x,y=i
        graph[x][y]=p #인구수 변경

result=0
while(True):
    count=0
    for i in range(n):
        for j in range(n):
            if visited[i][j]==0:
                if bfs(i,j)==-1:
                    count+=1
    if count==n*n:
        break
    visited=[[0]*n for _ in range(n)] #방문 초기화
    result+=1

print(result)

bfs함수 내에서 인구 수를 계속 더하고, 나라 수를 카운트 해서 연합 이후 인구수를 계산할 수 있게 했다

bfs함수 내의 while문이 끝나면, 연합한 나라의 인구 수를 바꿔준다

이것을 모든 땅에 대해 반복한다

.

.

이것을 또 무한반복하는데..  한번 모든땅을 반복할 때마다 날짜 수를 카운트 해주고,

모든 땅을 돌았는데 모든 땅에서 연합 불가능하다고 판단했을 경우 반복을 중단한다