[문제 풀이 24] 코드 트리 - n x n 표에서의 분배

n x n 표에서의 분배

 

• 문제 유형 : DFS
• 사용언어 : Python
• 난이도 : 실버 1
• 출처 : 코드 트리

 

https://www.codetree.ai/training-field/search/problems/distribution-in-an-n-x-n-table?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

from collections import deque
import sys

# 입력 받기
n, L, R = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]

def bfs(x, y, visited, grid, n, L, R):
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    queue = deque([(x, y)])
    component = []
    component.append((x, y))
    visited[x][y] = True
    
    while queue:
        cx, cy = queue.popleft()
        
        for dx, dy in directions:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                if L <= abs(grid[cx][cy] - grid[nx][ny]) <= R:
                    visited[nx][ny] = True
                    queue.append((nx, ny))
                    component.append((nx, ny))
    
    return component

def process(grid, n, L, R):
    visited = [[False]*n for _ in range(n)]
    components = []
    
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                comp = bfs(i, j, visited, grid, n, L, R)
                if len(comp) > 1:
                    components.append(comp)
    
    for comp in components:
        total_population = sum(grid[x][y] for x, y in comp)
        new_value = total_population // len(comp)
        for x, y in comp:
            grid[x][y] = new_value
    
    return len(components) > 0

count = 0
while True:
    if not process(grid, n, L, R):
        break
    count += 1

print(count)