[python] 백준 16234 인구 이동

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

16234번: 인구 이동

 

문제 해결

• 인구 이동이 진행될 때마다 계속 반복해서 진행하므로 시뮬레이션을 생각할 수 있다.
• 인구 이동 지역을 저장해야하므로 bfs를 이용해서 인구 이동 지역을 저장한후 평균을 그 지역 값에 넣어서 인구이동을 시킬 수 있다.
• 인구이동이 없으면 멈춰야한다. 이 부분에서 고민을 많이 했는데 이동한 지역이 없으면 인구 이동을 멈추는 변수 flag를 사용하여 인구 이동이 있으면 flag=1로 바꾸어 계속 진행하고 flag가 0으로 코드 끝에 유지되면 반복문을 종료하고 시간을 출력하면 된다.

 

CODE

from collections import deque
def bfs(a,b):
    que = deque()
    que.append((a,b))
    memo = [(a,b)]
    while que:
        x, y = que.popleft()
        for dx, dy in zip (dxs, dys):
            new_x = x + dx
            new_y = y + dy
            if 0<=new_x<n and 0<=new_y<n and visited[new_x][new_y]==0 and l<=abs(graph[new_x][new_y]-graph[x][y])<=r:
                visited[new_x][new_y] = 1
                memo.append((new_x,new_y))
                que.append((new_x,new_y))
    return memo
def simulate():
    global ans
    while True:
        flag = 0 # 반복문 종료: flag =0  반복문 유지 flag = 1
        for i in range(n):
            for j in range(n):
                visited[i][j] = 0
        for i in range(n):
            for j in range(n):
                if visited[i][j] ==0:
                    visited[i][j] = 1
                    c = bfs(i,j)
                    if len(c) > 1:
                        flag = 1
                        m_total = sum([graph[x][y] for x, y in c])//len(c)
                        for x, y in c:
                            graph[x][y] = m_total
        if flag ==0: 
            break
        ans += 1
    print(ans)
    return

if __name__=='__main__':
    n, l, r = map(int, input().split())
    graph = [list(map(int, input().split())) for _ in range(n)]
    visited = [[0]*n for _ in range(n)]
    dxs = [-1,1,0,0]
    dys = [0,0,-1,1]
    ans = 0
    simulate()