[백준] 16234번 (python 파이썬)

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

 

구현, BFS 문제이다.

 

처음에 문제를 이해했을 때 하루동안 2지역에서 인구이동이 일어났으면 2번 인구가 이동했을거라고 생각하고 풀었다.

이게아니라 

하루에 여러곳에서 인구가 이동했다고 해도 한번으로 인구이동이 발생했다고 친다.

 

하루에 이렇게 주황구역, 파란구역에서 인구 이동이 일어났으면 2번 발생한게 아니라 한번으로 친다. -> 하루에 한번이라도 어떤 구역에서 인구이동이 발생하면 한번으로 친다.

 

0,0 에서부터 bfs를 돌리고 n,n까지 돌린뒤 인구 이동이 발생했는치 체크하고

발생했으면 다시 0,0부터 bfs를 돌린다.

이동이 발생하지 않으면 무한루프를 멈춘다.

 

from collections import deque

n, l, r = map(int, input().split(' '))
graph = [list(map(int, input().split(' '))) for _ in range(n)]

d_x = [-1, 0, 1, 0]
d_y = [0, 1, 0, -1]

is_move = False


def bfs(c_x, c_y, visited, grpah):
    global is_move
    people = graph[c_x][c_y]
    count = 1
    queue = deque()
    queue.append((c_x, c_y))
    visited[c_x][c_y] = True
    temp = list()
    temp.append((c_x, c_y))

    while queue:
        pop_x, pop_y = queue.popleft()

        for i in range(4):
            n_x = pop_x + d_x[i]
            n_y = pop_y + d_y[i]

            if n_x < 0 or n_x >= n or n_y < 0 or n_y >= n:
                continue

            if visited[n_x][n_y]:
                continue

            if l <= abs(grpah[pop_x][pop_y] - grpah[n_x][n_y]) <= r:
                visited[n_x][n_y] = True
                queue.append((n_x, n_y))
                people += graph[n_x][n_y]
                count += 1
                temp.append((n_x, n_y))

    move_people = people // count

    if count > 1:
        is_move = True
        for x, y in temp:
            graph[x][y] = move_people

answer = 0

while True:
    is_move = False
    visited = [[False] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                bfs(i, j, visited, graph)

    if is_move:
        answer += 1
    else:
        break

print(answer)