[백준17144&파이썬] 시계 또는 반시계 방향으로 배열원소 회전하기 , 탐색 후 일괄업데이트

# 문제

백준 17144 미세먼지 안녕! 파이썬 풀이

17144번: 미세먼지 안녕!

# 코드

'''
  - 동시에 미세먼지 값들을 spread시킨다
  - spread시켰다면 공기청정기의 바람에 의해 이동시킨다.
'''

import sys
from collections import deque


def print2D(arr):
  for i in arr:
    print(i)


# ROW, COL, TIME
R, C, T = map(int, sys.stdin.readline().split())
board = list()

air_conditioner = []
for row in range(R):
  line = list(map(int, sys.stdin.readline().split()))
  board.append(line)

for row in range(R) :
  if board[row][0] == -1 :
    air_conditioner.append((row,0))

# print(air_conditioner)
dirs = [
  (-1,0), (0,1), (1,0), (0,-1)
  ]

reverse_dir = [
  (0,1), (-1,0), (0,-1),(1,0)
  ]
right_dir = [
  (0,1), (1,0), (0,-1), (-1,0)
  ]

def spread():
  global board, R, C, T
  dq = deque()

  # 미세먼지가 있는 시작점의 위치를 모두 파악한다.
  for row in range(R) :
    for col in range(C) :
      if board[row][col] > 0 : # 0보다 큰 곳이라면
        dq.append((row,col,board[row][col]//5)) # row,col, 퍼트릴 미세먼지

  # 미세먼지를 퍼트린다. 단 동시 시간대에 퍼트려야 한다.
  candidate= list()
  while len(dq) !=0 :
    poped = dq.popleft() # (row, col, 퍼트릴 미세먼지)

    spread_count = 0
    for dir in dirs :
      next = (poped[0] + dir[0], poped[1] + dir[1])
      if 0<= next[0] < R and 0<= next[1] < C and 0 <= board[next[0]][next[1]] :
        candidate.append((next[0],next[1],poped[2])) # 퍼트려진 미세먼지 후보군에 저장
        spread_count +=1
    candidate.append((poped[0],poped[1], poped[2]*spread_count*-1)) # 현재 위치에서 뺴야할 것

  # 퍼트린 미세먼지 기반으로 board를 업데이트 한다.
  for item in candidate : # (row,col,updating_num)
    board[item[0]][item[1]] += item[2]


def run_air() :
  global board, R, C, T, air_conditioner

  for i in range(2) :
    before = (air_conditioner[i][0],0,0)
    if i == 0 :
      mdir = reverse_dir
    else :
      mdir = right_dir

    for dir in mdir :
      while True :
        cur = (before[0] + dir[0], before[1] + dir[1])
        if 0<= cur[0] < R and 0<= cur[1] < C :
          if board[cur[0]][cur[1]] == -1 : # 공기청정기가 존재하는 위치일때
            break
          temp = (cur[0], cur[1],board[ cur[0] ][ cur[1] ] )
          board[cur[0]][cur[1]] = before[2]
          before = temp
        else :
          break


for t in range(T) :
  spread()
  run_air()

# 미세먼지의 갯수를 센다
result = 0
for row in range(R) :
  for col in range(C) :
    if board[row][col] > 0 :
      result += board[row][col]

print(result)

# 풀이

• 크게 보면 두가지 조건을 구현하면 되는 구현 + 시뮬레이션 문제이다. 그래프탐색과 같은 개념도 필요 없다. 저번에 다뤘던 일괄업데이트 개념을 안다면 미세먼지가 spread()되는 과정의 구현은 어렵지 않을 것이다.
• 정말 정직하게 두가지만 구현하면 되는게 정답 소스코드를 아래와 같이 분리해서 풀었다. 

for t in range(T) :
  spread()
  run_air()

• 먼저 미세먼지를 확산 시킨다. 미세먼지 시작위치를 기록하고 해당 위치로부터 4방향으로 조건에 맞게 확산시키고, 현재 위치는 확산된것만큼 빼준다. 대신 이걸 바로 업데이트 하면안되고 candidate후보군을 두고 일괄로 업데이트 시켜야 한다. 
• 내가 고민을 한 것은 공기청정기의 바람에 따라서 순환 및 흡입 되는 과정이다. 먼저 시계방향과 반시계 방향을 가리키는 right_dir, reverse_dir를 아래와 같이 만들었다.

reverse_dir = [
  (0,1), (-1,0), (0,-1),(1,0)
  ]
right_dir = [
  (0,1), (1,0), (0,-1), (-1,0)
  ]

• 이후 순환하는 코드는 똑같이 작성하고 방향만 다르게 돌게하여 코드 중복을 해결하려고 했다. 그래서 이 방향을 가리키는 배열을 아래와 같이 적용해 활용했다.

  for i in range(2) :
    before = (air_conditioner[i][0],0,0)
    if i == 0 :
      mdir = reverse_dir
    else :
      mdir = right_dir
      
    for dir in mdir :
     # 순환하는 조건을 여기에서 구현한다. mdir을 지정했기에 코드 재활용이 가능했다.

• 처음 순환관련 코드를 작성할때 잘못 접근했던 것이 before, cur, next를 한 반복에서 다루었다. 근데 이렇게 생각하면 당연히 안됐다. 
• 기준점을 before로 잡고 dir을 통해 구한 다음 위치를 cur이라 지정했다.
• before의 값을 cur에 옮긴다. 이때 cur값이 사라져버리면안되기 때문에 temp에 미리 복사하여 저장시켜 놓았다. 
• before값을 cur에 옯겼다면 cur은 다음 반복에서 다시 before가 되어야 하기 때문에 cur을 before로 다시 바꾸어놓았다.
• 이때 순환의 종료조건에 대해서 생각해야 한다. cur가 공기정정기 위치에 도달하면 cur을 before의 값으로 바꾸면 안된다. 바꿀경우 공기청정기가 사라진다.
• 또한 순환에서 만나는 -1은 무조건 mdir의 마지막 이동방향이다. 그렇기 때문에 아래와 같이 cur이 -1이 될때 반복을 종료 시켜 버린다.

      while True :
        cur = (before[0] + dir[0], before[1] + dir[1])
        if 0<= cur[0] < R and 0<= cur[1] < C :
          if board[cur[0]][cur[1]] == -1 : # 공기청정기가 존재하는 위치일때
            break

• 오랜만에 재밌는 구현문제를 풀어서 기분 좋았다.