공기청정기 - 확산 알고리즘

문제

---

세로 길이 N, 가로 길이 M 인 2차원 배열이 주어진다.

이 배열의 각 칸에 들어있는 수는 1초에 한번씩 자기 자신을 나눠서 x, y좌표와의 거리가 1이상 k이하인 칸들에 더해준다. 두 점 (x1, y1), (x2, y2)의 거리는 |x1-x2| + |y1-y2|로 구한다. 이때 주변에 나눠주는 값은 현재 그 칸에 있는 값을 2 k2 + 2 k + 1로 나눈 몫이고, 주변에 나눠준 만큼 원래 있던 값은 줄어들게 된다.

예를 들어, 아래 그림에서 k가 1이라면 t = 0의 (2,1)위치에 있는 8은 8/5의 몫인 1을 주변에 있는 세 칸에 나눠주고, 자기자신은 3만큼 줄어든다.

t초가 지난 후 배열의 상태를 출력하여라.

입력

---

첫 번째 줄에 N, M, k 가 주어진다.

두 번째 줄부터 N 줄에 걸쳐 배열의 값이 주어진다.

마지막 줄에 t 가 주어진다.

(1 ≤ N, M ≤ 5, 1 ≤ k ≤ 4, 1 ≤ 배열의 값 ≤ 10, 1 ≤ t ≤ 3)

출력

---

t 초 후 배열을 출력한다.

입력의 예 1

3 4 1
5 1 3 4
2 5 1 2
7 8 3 1
2

출력의 예 1

4 3 3 4
3 4 2 2
6 5 5 1

입력의 예 2

3 3 1
2 4 2
4 2 4
2 4 2
3

출력의 예 2

2 4 2
4 2 4
2 4 2

입력의 예 3

2 5 2
10 10 10 10 10
10 10 10 10 10
5

출력의 예 3

10 10 10 10 10
10 10 10 10 10

입력의 예 4

3 4 2
17 18 11 12
16 19 17 15
18 18 13 18
10

출력의 예 4

16 16 15 15
16 16 13 18
17 17 18 15

 

풀이

 - n칸 확산문제에서 조건문인 나눠줘야 할 값(divide_value) 만들어서 now_value에 계산 주변 값에 더해 주기 

import copy

def move_all_scope_direction(row, colum, map_data, scope) :
  
  result_list = copy.deepcopy(map_data)                 #누적 계산을 위해서 깊은 복사
  
  for px in range(row) :                                #기준점 x좌표인 py, y좌표인 py
    for py in range(colum):                             #0, 0부터 시작하면서 map_data[0][0]부터 거리값(score) 만큼 확산 시작
      divide_value = (2*scope*scope) + (2*scope) + 1    #나눌 계산 식
      now_value = map_data[px][py]                      #현재 기준 값
      given_value = now_value // divide_value           #현재 기준 값으로 부터 나눌 몫 계산
      
      for sx in range(row) :                            #범위 좁힐 필요 있음
        for sy in range(colum) :
          scope_x = abs(px-sx)
          spred_y = abs(py-sy)
          for scope_num in range(1, scope+1) :          #scope의 절대값 만큼 확산
            if scope_x + spred_y == scope_num :
              if given_value > 0 :                      #나눌 몫이 0보다 큰경우에만 나눔
                result_list[sx][sy] += given_value      #주변에 나눠준다
                result_list[px][py] -= given_value      #나눈 만큼 본인에서 빼줌
  return result_list
  
if __name__ == "__main__":
  row, colum, scope = map(int, input().split())
  data_list = []
  
  for i in range(row) :
    data_list.append(list(map(int, input().split())))
  
  result_list = []
  time = int(input())
  
  for i in range(time) :
    data_list = move_all_scope_direction(row, colum, data_list, scope)
  
  for i in range(row) :
    print(" ".join(map(str, data_list[i])))