백준 구현 대비 미세먼지 안녕

문제:https://www.acmicpc.net/problem/17144

접근

1초동안 다음과 같은 일이 순서대로 발생함
1.미세먼지의 확산
2.공기청정기의 정화작업

이 두 순서대로 도식화를 진행하면 된다.
처음에는 별다른 알고리즘 로직이 필요해 보이지 않아서 간단하게 구현할 수 있을것이라고 생각하였으나 예상외로 디버깅하는데 시간이 많이 걸렸다. 아무리 돌려봐도 문제가 보이지않아 결국 구글링.. 문제는 dust 함수에 있었음

dust함수

def dust(graph,R,T):
  movelist=[[1,0],[0,1],[-1,0],[0,-1]]
  dustlist=[]
  for i in range(R):
    for j in range(T):
      if graph[i][j]>0:
        dustlist.append([i,j])

  for du in dustlist:
    total=graph[du[0]][du[1]]
    a=0
    for mo in movelist:
      ni,nj=du[0]+mo[0],du[1]+mo[1]
      if 0<=ni<R and 0<=nj<T and graph[ni][nj]!=-1:
        graph[ni][nj]+=total//5
        a+=total//5
    graph[du[0]][du[1]]-=a

dust 함수의 문제점은 다음과 같다. 문제에서 미세먼지는 동시에 확산된다고 적혀있다. 동시에 확산된다는 것이 의미하는 것은 각각의 미세먼지의 확산이 다른 미세먼지 확산의 결과물값에 영향을 주면 안된다는 소리이다. 즉 이게 의미하는것은 원래 그래프의 미세먼지값, 여기서는 dustlist 의 원소들을 좌표로 하는 그래프의 위치값이 변하면 안된다는 의미이다.

  for du in dustlist:
    total=graph[du[0]][du[1]]
    a=0
    for mo in movelist:
      ni,nj=du[0]+mo[0],du[1]+mo[1]
      if 0<=ni<R and 0<=nj<T and graph[ni][nj]!=-1:
        graph[ni][nj]+=total//5
        a+=total//5
    graph[du[0]][du[1]]-=a

그러나 위의 dust함수의 반복문에서 graph값을 직접적으로 변화시키고 있다. 그 결과 그래프의 미세먼지값들이 오염되게 되고 정상적인 실행결과가 불가능해진다. 즉 원래 그래프와 독립적인 또 하나의 그래프를 선언한후, 새로 선언한 그래프와 원래 그래프의 값을 더해주는 과정이 필요하다.

def spread(board):  # 1초마다 미세먼지가 퍼지는 동작
  dx = [-1,0,1,0]
  dy = [0,1,0,-1]

  change = [[0] * C for _ in range(R)]

  for x in range(R):
      for y in range(C):
          if board[x][y] > 0: # 미세먼지가 있는 경우
              tmp = 0
              for i in range(4):  # 4방면으로 퍼짐
                  ax = x + dx[i]
                  ay = y + dy[i]
                  if 0 <= ax < R and 0 <= ay < C:  # board 에서 벗어나지 않는 범위일 경우만
                      if board[ax][ay] != -1:  # 공기청정기가 아닌 위치만 확산
                          change[ax][ay] += board[x][y]//5
                          tmp += board[x][y]//5
              board[x][y] -= tmp
  for x in range(R):
      for y in range(C):
          board[x][y] += change[x][y]



def air(graph,R,T):
  airlist=[]
  for i in range(R):
    for j in range(T):
      if graph[i][j]==-1:
        airlist.append([i,j])
  
  # 처음온게 위에있는거
  # 처음 시계방향
  fi,fj=airlist[0][0],airlist[0][1]
  ci,cj=fi,fj
  rotate=[[0,1],[-1,0],[0,-1],[1,0]]
  toplist=[]
  check=False
  for ro in rotate:
    while 0<=fi+ro[0]<R and 0<=fj+ro[1]<T:
      fi,fj=fi+ro[0],fj+ro[1]
      if fi==ci and fj==cj:
        check=True
        break
      toplist.append([fi,fj])
    if check:
      break

  fi,fj=airlist[1][0],airlist[1][1]
  ci,cj=fi,fj
  rotate=[[0,1],[1,0],[0,-1],[-1,0]]
  botlist=[]
  check=False
  for ro in rotate:
    while 0<=fi+ro[0]<R and 0<=fj+ro[1]<T:
      fi,fj=fi+ro[0],fj+ro[1]
      if fi==ci and fj==cj:
        check=True
        break
      botlist.append([fi,fj])
    if check:
      break
  
  newgraph=[item[:] for item in graph]

  for i in range(len(toplist)-1):
    newgraph[toplist[i+1][0]][toplist[i+1][1]]=graph[toplist[i][0]][toplist[i][1]]
  newgraph[toplist[0][0]][toplist[0][1]]=0

  for i in range(len(botlist)-1):
    newgraph[botlist[i+1][0]][botlist[i+1][1]]=graph[botlist[i][0]][botlist[i][1]]
  newgraph[botlist[0][0]][botlist[0][1]]=0
  return newgraph

def total(graph):
  to=0
  for g in graph:
    to+=sum(g)
  return to
  


R,C,T=map(int, input().split())
graph=[]
count=0
for i in range(R):
  graph.append(list(map(int, input().split())))
while count<T:
  spread(graph)
  graph=air(graph,R,C)
  count+=1

print(total(graph)+2)

+추가로 매개변수를 선언해서 함수로 전달하는 것보다 전역변수를 적절히 활용하는 습관을 들여야함