백준 16234) 인구이동 (골드.5)

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

16234번: 인구 이동

문제의 유형은 그래프 탐색을 이용하여 연결된 부분을 탐색하는 우선탐색의 문제이다. 

문제의 조건은 다음과 같다. 

1) 상하좌우로 인접한 두 나라의 인구차가 L보다 크거나 같고 R보다 작거나 같으면 국경선이 열린다. 

2) 조건에 해당하여 국경선이 열린 모든 나라를 연합이라고 한다. 

3) 국경선이 열리면 인구이동에 의해 연합 각국의 인구수는 연합국의 인구수 총합 // 연합국의 수 가 된다. 

4) 한번의 인구이동에는 1일이 걸린다. 

5) 모든 국가에서 인구이동이 이루이지지 않을 때까지 반복한다. 

 

 

 

bfs를 이용하여 연합국이 될수 있는 모든 나라를 탐색하고 모든 연합국에 대해서 연합국 인구의 총합 // 연합국의 수로 값을 변경해준다. 모든 국가에 대해서 인구이동이 이루어 지지 않을 때까지 반복해야 하므로 while문을 이용하였다. 

from collections import deque
import sys 

def bfs(x, y, open):
    queue = deque()
    queue.append((x, y))
    check[x][y] = 1
    open.add((x, y))
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            ny = y + d[i][0]
            nx = x + d[i][1]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if l <= abs(data[nx][ny] - data[x][y]) <= r and not check[nx][ny]:
                queue.append((nx, ny))
                check[nx][ny] = 1
                open.add((nx, ny))
    if len(open) >1 :
        temp = sum([data[y][x] for y, x in open]) //len(open)
        for y, x in open:
            data[y][x] = temp
        return True

    else:
        return False

n, l, r = map(int, sys.stdin.readline().split())
data = [list(map(int, input().split())) for _ in range(n)]

d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
result, flag = 0, True
while flag:
    check = [[0]*n for _ in range(n)]
    flag = False
    for i in range(n):
        for j in range(n):
            if not check[i][j] and bfs(i, j, set()):
                flag = True
    if flag:
        result += 1
print(result)