이번 문제는 삼성 기출 문제로 BFS를 통해 개방할 수 있는 국경선들을 모두 체크하고, 현재 위치의 나라와 연결된 모든 나라들을 구하여 그 나라들의 인구수를 평균값으로 갱신해준다. 이 과정을 거치기 전의 전체 나라들의 인구 상황을 저장하고, 이 과정을 거친 후의 인구 상황과 비교하여 둘이 같을 때가지 반복하여 진행하였다.

• n, l, r을 입력받는다.
• ground를 입력받는다.
• dy, dx에 4가지 방향을 저장한다.
• bfs함수를 sy, sx를 인자로 갖도록 선언한다.
  -> q를 deque로 선언한다.
  -> q에 (sy, sx)를 넣는다.
  -> visited[sy][sx]를 1로 갱신한다.
  -> 연결된 나라들의 인구수를 저장할 변수 total을 ground[sy][sx]로 선언한다.
  -> 연결된 나라들의 위치를 저장할 리스트 cnt를 선언하고 (sy, sx)를 넣는다.
  -> q가 존재할 동안 반복하는 while문을 돌린다.
  --> q에서 y, x를 추출한다.
  --> 4번 반복하는 i에 대한 for문을 돌린다.
  ---> ny, nx를 y+dy[i], x+dx[i]로 선언한다.
  ---> 만약 ny, nx가 0 이상, n 미만이고, visited[ny][nx]가 0이고, ground[y][x]-ground[ny][nx]의 절댓값이 l 이상, r 이하일 경우,
  ----> visited[ny][nx]를 1로 갱신한다.
  ----> total에 ground[ny][nx]를 더한다.
  ----> cnt에 (ny, nx)를 넣는다.
  ----> q에 (ny, nx)를 넣는다.
  -> cnt를 순회하는 i, j에 대한 for문을 돌린다.
  --> ground[i][j]를 total//len(cnt)로 갱신한다.
• answer를 0으로 선언한다.
• 계속 반복하는 while문을 돌린다.
  -> tmp에 ground를 deepcopy하여 저장한다.
  -> 방문처리 리스트 visited를 n*n 크기로 선언하고 0으로 채운다.
  -> n번 반복하는 i에 대한 for문을 돌린다.
  --> n번 반복하는 j에 대한 for문을 돌린다.
  ---> 만약 visited[i][j]가 0일 경우,
  ----> bfs(i, j)를 호출한다.
  -> 만약 tmp가 ground와 다를 경우,
  --> answer를 1 증가시킨다.
  -> 그 외의 경우,
  --> while문을 탈출한다.
• answer를 출력한다.

Code

from collections import deque
from copy import deepcopy
n, l, r=map(int, input().split())
ground=[list(map(int, input().split())) for _ in range(n)]
dy, dx=[1, 0, -1, 0], [0, 1, 0, -1]
def bfs(sy, sx):
    q=deque()
    q.append((sy, sx))
    visited[sy][sx]=1
    total=ground[sy][sx]
    cnt=[(sy, sx)]
    while q:
        y, x=q.popleft()
        for i in range(4):
            ny, nx=y+dy[i], x+dx[i]
            if 0<=ny<n and 0<=nx<n and not visited[ny][nx] and l<=abs(ground[y][x]-ground[ny][nx])<=r:
                visited[ny][nx]=1
                total+=ground[ny][nx]
                cnt.append((ny, nx))
                q.append((ny, nx))
    for i, j in cnt:
        ground[i][j]=total//len(cnt)
answer=0
while True:
    tmp=deepcopy(ground)
    visited = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                bfs(i, j)
    if tmp!=ground:
        answer+=1
    else:
        break
print(answer)