인구 이동

 

 

 

 

문제 유형 파악 및 구현

이 문제 또한 차분하게 풀 필요가 있는 문제이다.

BFS를 통해 조건에 맞는 노드들을 그룹짓고 마지막에 변환해주는 간단한 프로그램이지만 고려해야될 부분이 많아 약간 시간을 썼던 것 같다. 이런 문제는 항상 느끼는 거지만 급하지 않게 차분히 하는게 중요하다.

 

 

 

코드

n, min_value, max_value = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(map(int,input().split())))


from collections import deque


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

while(1):
    again_check = False
    check = [[0]*n for _ in range(n)]
    q = deque()
    group = 0
    change_list = []
    for x in range(n):
        for y in range(n):
            if check[x][y] != 0:
                continue
            q.append([x, y])
            group += 1
            check[x][y] = group
            sum_result = graph[x][y]
            count_result = 1
            while q:
                now_x, now_y = q.popleft()
                for i in range(4):
                    next_x = now_x + dx[i]
                    next_y = now_y + dy[i]
                    if next_x < 0 or next_x >= n or next_y < 0 or next_y >= n:
                        continue
                    if check[next_x][next_y] != 0:
                        continue
                    if min_value <= abs(graph[next_x][next_y]-graph[now_x][now_y]) <= max_value:
                        check[next_x][next_y] = group
                        q.append([next_x, next_y])
                        again_check = True
                        sum_result += graph[next_x][next_y]
                        count_result += 1
            change_list.append(sum_result/count_result)
    
    if again_check == False:
        break

    for change in range(1, group+1):
        for x in range(n):
            for y in range(n):
                if check[x][y] == change:
                    graph[x][y] = int(change_list[change-1])
    
    real_count += 1

print(real_count)