[BOJ] 미세먼지 안녕


  • BOJ의 미세먼지 문제 풀이입니다

문제 풀이

  • 문제를 풀기 위해서는 미세먼지 확산과 공기청정기 순환을 구현해주어야 합니다

  • 미세먼지 확산

    • 공기청정기는 두칸을 차지하고 위쪽 공기청정기는 반시계 방향, 아래쪽 공기청정기는 시계 방향으로 순환합니다
    • 따라서 각각의 공기청정기 순환 결과를 구현해주어야 합니다

    • 확산하는 경우 모든 칸에서 한번에 확산이 일어나기 때문에 별도의 배열 matrix_dust를 만들고 확산 결과를 해당 배열에 저장해줍니다
    def diffusion(r,c):
      diff_value = matrix[r][c] // 5
      direction_count = 0 # 총 몇칸으로 확산되었는지 count 하기 위한 변수
    
      # bottom
      if(r+1 < R and matrix[r+1][c] != -1):
          matrix_dust[r+1][c] = matrix_dust[r+1][c] + diff_value
          direction_count+=1
    
      # top
      if(r-1 >= 0 and matrix[r-1][c] != -1):
          matrix_dust[r-1][c] = matrix_dust[r-1][c] + diff_value
          direction_count+=1
    
      # right
      if(c+1 < C and matrix[r][c+1] != -1):
          direction_count+=1
          matrix_dust[r][c+1] = matrix_dust[r][c+1] + diff_value
    
      # left
      if(c-1 >=0  and matrix[r][c-1] != -1):
          matrix_dust[r][c-1] = matrix_dust[r][c-1] + diff_value
          direction_count+=1
    
      #
      matrix_dust[r][c] = matrix_dust[r][c] +  matrix[r][c] - (direction_count * diff_value)
    
    
    
    • 위쪽 공기청정기가 순환할 때 아래 방향 -> 왼쪽 방향 -> 위쪽 방향 -> 오른쪽 방향 순으로 이동하는 것으로 구현해줍니다
    def purify_move1(air):
      # down
      for r in range(air-1,-1,-1):
          if(matrix_dust[r+1][0] != -1 ):
              matrix_dust[r+1][0] = matrix_dust[r][0]
              matrix_dust[r][0] = 0
    
      # left
      for c in range(1,C):
          matrix_dust[0][c-1] = matrix_dust[0][c]
          matrix_dust[0][c] = 0
    
      # top
      for r in range(1, air+1):
          matrix_dust[r-1][C-1] = matrix_dust[r][C-1]
          matrix_dust[r][C-1] = 0
    
      #right
      for c in range(C-2, 0, -1):
          matrix_dust[air][c+1] = matrix_dust[air][c]
          matrix_dust[air][c]=0
    
    
    • 아래쪽 공기청정기가 순환할 때는 위쪽 방향 -> 왼쪽 방향 -> 아래쪽 방향 -> 오른쪽 방향 순으로 이동하는 것으로 구현해줍니다
    
    def purify_move2(air):
      # top
      for r in range(air+1, R):
          if(matrix_dust[r-1][0] != -1):
              matrix_dust[r-1][0] = matrix_dust[r][0]
              matrix_dust[r][0] = 0
    
      # left
      for c in range(1,C):
          matrix_dust[R-1][c-1] = matrix_dust[R-1][c]
          matrix_dust[R-1][c] = 0
    
      # down
      for r in range(R-2, air-1, -1):
          matrix_dust[r+1][C-1] = matrix_dust[r][C-1]
          matrix_dust[r][C-1] = 0
    
      # right
      for c in range(C-2, 0, -1):
          matrix_dust[air][c+1] = matrix_dust[air][c]
          matrix_dust[air][c] = 0
    
    

전체 코드

import sys

R, C, T = map(int, sys.stdin.readline().split())

matrix = []
for _ in range(R):
    matrix.append(list(map(int, sys.stdin.readline().split())))

air = []

for i in range(R):
    for j in range(C):
        if(matrix[i][j] == -1):
            air.append(i)


def purify_move1(air):
    # down
    for r in range(air-1,-1,-1):
        if(matrix_dust[r+1][0] != -1 ):
            matrix_dust[r+1][0] = matrix_dust[r][0]
            matrix_dust[r][0] = 0

    # left
    for c in range(1,C):
        matrix_dust[0][c-1] = matrix_dust[0][c]
        matrix_dust[0][c] = 0

    # top
    for r in range(1, air+1):
        matrix_dust[r-1][C-1] = matrix_dust[r][C-1]
        matrix_dust[r][C-1] = 0

    #right
    for c in range(C-2, 0, -1):
        matrix_dust[air][c+1] = matrix_dust[air][c]
        matrix_dust[air][c]=0


def purify_move2(air):
    # top
    for r in range(air+1, R):
        if(matrix_dust[r-1][0] != -1):
            matrix_dust[r-1][0] = matrix_dust[r][0]
            matrix_dust[r][0] = 0

    # left
    for c in range(1,C):
        matrix_dust[R-1][c-1] = matrix_dust[R-1][c]
        matrix_dust[R-1][c] = 0

    # down
    for r in range(R-2, air-1, -1):
        matrix_dust[r+1][C-1] = matrix_dust[r][C-1]
        matrix_dust[r][C-1] = 0

    # right
    for c in range(C-2, 0, -1):
        matrix_dust[air][c+1] = matrix_dust[air][c]
        matrix_dust[air][c] = 0




# 확산을 위한 함수
def diffusion(r,c):
    diff_value = matrix[r][c] // 5
    direction_count = 0

    # bottom
    if(r+1 < R and matrix[r+1][c] != -1):
        matrix_dust[r+1][c] = matrix_dust[r+1][c] + diff_value
        direction_count+=1

    # top
    if(r-1 >= 0 and matrix[r-1][c] != -1):
        matrix_dust[r-1][c] = matrix_dust[r-1][c] + diff_value
        direction_count+=1

    # right
    if(c+1 < C and matrix[r][c+1] != -1):
        direction_count+=1
        matrix_dust[r][c+1] = matrix_dust[r][c+1] + diff_value

    # left
    if(c-1 >=0  and matrix[r][c-1] != -1):
        matrix_dust[r][c-1] = matrix_dust[r][c-1] + diff_value
        direction_count+=1

    # 반복문을 통해서 한칸 씩 움직이면서 확산되기 때문에 matrix_r[r][c]에서 확산할 때
    # 이미 matrix_r[r][c]에 값이 있을 수 있으므로, 해당 값을 더해준다
    matrix_dust[r][c] = matrix_dust[r][c] +  matrix[r][c] - (direction_count * diff_value)







for _ in range(T):
    # 공기 청정기 위치 저장
    matrix_dust = [[0]*C for _ in range(R)] # 확산 결과 저장하기 위한 행렬
    matrix_dust[air[0]][0] = -1
    matrix_dust[air[1]][0] = -1

    for r in range(R):
        for c in range(C):
            if(matrix[r][c] != -1 and matrix[r][c] != 0):
                # 1, 확산
                diffusion(r,c)

    # 2, 공기청정기 작동
    purify_move1(air[0]) # 윗칸 공기청정기
    purify_move2(air[1]) # 아래칸 공기청정기
    matrix = matrix_dust # 바뀐 결과를 저장해준다

count = 0

for i in range(R):
    for j in range(C):
        if(matrix[i][j] != -1):
            count+=matrix[i][j]

print(count)




Reference









© 2020. by dkmqflx

Powered by dkmqflx