[BOJ-16234] 인구이동

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

16234번: 인구 이동

---

[풀이]

예제 5번을 잘 이해해보고 풀어보자.

N=4, L=10, R= 50

A=[[10 ,100, 20, 90], [80, 100, 60, 70], [70, 20, 30, 40], [50, 20, 100, 10]]

출력: 3

 

먼저 각 지역 인구차이가 L~R을 만족하는 그룹들을 먼저 찾는다.

그룹이 한개라면 문제에서 보여준 예제대로 (연합의 인구수)/(연합을 이루는 칸 개수) 로 

A값을 업데이트하면된다.

 

그렇다면 그룹이 여러개가 존재한다면 어떻게 해야할까?

마찬가지로 각 그룹별로 (통합후인구합)/(연결된 네모칸 개수) 로 A의 값을 업데이트한다.

 

A배열 (인구이동 횟수 0회)

A배열이 위의 그림과 같다.

먼저 현위치의 상/하/좌/우 중 하나가 L과 R사이라면

BFS연산을 한다.

 

현위치 (y,x)라 할때, 현위치가 아직 방문하지 않은 상태여야한다.

현위치의 상/하/좌/우 위치를 (nexty, nextx)라 하자

L(10)<= abs(A[nexty][nextx]-A[y][x])<=R (50) 인 것을 만족한 상/하/좌/우 위치가 하나라도 있다면

위치 (y,x)를 시작점으로 BFS연산을 한다는 것이다.

그리고 하나라도 있기때문에, 인구이동 한번 하게 된다.

인구이동을 한뒤에 앞으로도 계속 이동할지 따져야한다.

 

여기서 BFS연산도 마찬가지로

현위치의 상/하/좌/우 가 아직 방문되지 않은 상태이고

조건 L(10)<= abs(A[nexty][nextx]-A[y][x])<=R (50)을 만족하는지 확인해야한다.

그러면 초기배열 A=[[10 ,100, 20, 90], [80, 100, 60, 70], [70, 20, 30, 40], [50, 20, 100, 10]]은 

위의 그림과 같이 조건을 만족하는 연결그룹 1개를 얻을 수 있다.

 

그리고 BFS함수를 실행중 현위치의 방문여부를 따진 뒤

방문 후에 현재위치(y,x, A[y][x])를 unions라는 리스트에 저장을했다. 

unions의 목적은 나중에 연결된 그룹들의 값을 갱신해야한다.

 

연합의 인구수=unions의 2번째원소들 원소값 총합

연합을 이루고 있는 칸의개수= len(unions)

갱신값= int(연합의 인구수 / 연합을 이루고 있는 칸의 개수)

 

 

 

 

 

 

 

---

[코드]

import sys
from collections import deque
input=sys.stdin.readline
q=deque()

#상/하/좌/우
dy=(-1,1,0,0)
dx=(0,0,-1,1)

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

def isRange(y,x):
    global N
    if (y>=0 and y<N) and (x>=0 and x<N):
        return True
    return False

def bfs(y,x):
    global L,R,A,N, visited
    unions=[]
    q.append((y,x))
    while q:
        y,x=q.popleft()
        if not visited[y][x]:
            visited[y][x]=True
            unions.append((y,x,A[y][x]))
            for i in range(4):
                nexty, nextx=y+dy[i], x+dx[i]
                if isRange(nexty, nextx):
                    if (L<=abs(A[nexty][nextx]-A[y][x])<=R) and (not visited[nexty][nextx]):
                        q.append((nexty,nextx))
           
    union_sum=0
    for i in range(len(unions)):
        union_sum+=unions[i][2]

    union_sum=int(union_sum/len(unions))
    for i in range(len(unions)):
        A[unions[i][0]][unions[i][1]]=union_sum


def solution():
    global N,L,R,A, visited
    #나라가 1개밖에 없으므로 인구이동할 필요가 없다.
    if N==1:
        return 0
    
    result=0
    while True:
        visited=[[False]*N for _ in range(N)]
        keep_loop=False
        for y in range(N):
            for x in range(N):
                if not visited[y][x]:
                    cnt=0
                    for i in range(4):
                        nexty=y+dy[i]
                        nextx=x+dx[i]
                        if isRange(nexty, nextx):
                            if L<=abs(A[nexty][nextx]-A[y][x])<=R:
                                cnt+=1
                                break
                    #상/하/좌/우 중  현재위치의 인구수차이가 L~R사이가 최소 한개라도 있다면.
                    if cnt>0:
                        bfs(y,x)
                        keep_loop=True
       
        if not keep_loop:
            break
        result+=1
    return result
    
def main():
    print(solution())
    
if __name__=='__main__':
    main()