100년 뒤 개발자 한승규입니다.

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

평범한 그래프 문제였지만, 이동이 있었는지 체크하며 수를 하나씩 늘리는 과정이 좀 귀찮았다.

한 차례마다 각 칸에 대하여

위, 아래, 좌, 우 이렇게 4방향을 확인하고 만약 차이가 범위 내라면 그래프 탐색을 실행한다.

탐색을 진행하가며 인구수를 더해주고 탐색이 끝나면 총 인구를 칸으로 나누어 인구를 분배한다.

만약 해당 차례에 인구의 이동이 없었다면, 반복문을 종료하고 지금까지 소모한 턴을 출력한다.

import sys
from collections import deque

dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]

N, L, R = map(int, sys.stdin.readline().split())

nation = list()

for _ in range(N):
    nation.append(list(map(int, sys.stdin.readline().split())))

flag = True

result = 0

while flag:

    flag = False

    visited = [[False for _ in range(N)] for _ in range(N)]

    for r in range(N):
        for c in range(N):
            if visited[r][c] is False:

                visited[r][c] = True

                need_visit = deque()
                change = [[r, c]]

                need_visit.append([r, c])

                people = nation[r][c]

                while need_visit:

                    cur_r, cur_c = need_visit.popleft()

                    for d in range(4):
                        next_r, next_c = cur_r + dx[d], cur_c + dy[d]
                        if 0 <= next_r < N and 0 <= next_c < N and visited[next_r][next_c] is False and L <= abs(nation[cur_r][cur_c] - nation[next_r][next_c]) <= R:
                            change.append([next_r, next_c])
                            visited[next_r][next_c] = True
                            need_visit.append([next_r, next_c])
                            people += nation[next_r][next_c]
                            flag = True

                per_people = people // len(change)

                for next_r, next_c in change:
                    nation[next_r][next_c] = per_people

    if flag:
        result += 1

print(result)