문제 링크

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

문제 설명

• 인접한 좌표 간 인구가 일정 범위 안에 있는 것들끼리 평균 값으로 인구 이동
• 이동 횟수 출력

풀이

• DFS로 연합마다 번호를 매김
• 각 연합에 해당하는 값을 평균 값으로 갱신
• 연합이 생기지 않을 때까지 반복

느낀 점

• 알고리즘이 어려운건 없었던 것 같다

코드

def init():
    import sys
    ipt = sys.stdin.readline
    n, l, r = map(int, ipt().split())
    board = []
    for _ in range(n):
        row = list(map(int, ipt().split()))
        board.append(row)
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    return n, l, r, board, 0, dx, dy


def dfs(start):
    sy, sx = start
    union[sy][sx] = num
    sum_list[num][0] += board[sy][sx]
    sum_list[num][1] += 1
    for i in range(4):
        ny = sy + dy[i]
        nx = sx + dx[i]
        if 0 <= ny < n and 0 <= nx < n:
            if not union[ny][nx]:
                if l <= abs(board[ny][nx] - board[sy][sx]) <= r:
                    dfs((ny, nx))


def move():
    for i in range(n):
        for j in range(n):
            board[i][j] = sum_list[union[i][j]][0] // sum_list[union[i][j]][1]


n, l, r, board, count, dx, dy = init()
while True:
    num = 1
    union = [[0] * n for _ in range(n)]
    sum_list = [[0, 0] for _ in range(n**2+1)]
    for i in range(n):
        for j in range(n):
            if not union[i][j]:
                dfs((i, j)) 
                num += 1
    if union[-1][-1] == n**2:
        break
    move()
    count += 1
print(count)