백준 17144 미세먼지 안녕!

Ddudduu·2023년 9월 19일

문제

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

1초 동안 아래 적힌 일이 순서대로 일어난다.

미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
- (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
- 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
- 확산되는 양은 Ar,c/5이고 소수점은 버린다.
- (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
공기청정기가 작동한다.
- 공기청정기에서는 바람이 나온다.
- 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
- 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
- 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

입력

첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.

둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

출력

첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

풀이

1. 맵을 입력받고 공기청정기 좌표를 저장한다.

2. 확산

a. 인접 4방향에 대해서
b. 공기청정기 있거나 맵 벗어나는지 확인
c. 인접 칸에 board[x][y] // 5 만큼 확산
d. board[x][y] -= (board[x][y]//5) * 확산된 방향의 개수
⭐주의할 점은 마지막에 기존 맵에 확산된 양을 더해주는 것이다.
처음부터 기존 맵에 더해버리면, 원래 값 + 확산된 값이 다시 확산될 수도 있기 때문에 확산돼서 증가된 양은 따로 저장해줘야 한다!

def spread():
	# 확산된 양 저장할 2차원 배열
	spread = [[0]*c for i in range(r)]
  
	for x in range(r):
  	for y in range(c):
      	# 먼지가 있다면
      	if board[x][y] > 0:
          	spreadAmount = board[x][y] // 5
              
          	for k in range(4):
              	nx = x + dx[k]
                  ny = y + dy[k]
                  
                  if nx < 0 or nx >= r or ny < 0 or ny >= c:
                  	continue
                  # 공기청정기 있다면 패스
                  if board[nx][ny] == -1:
                  	continue
                      
                  # 인접칸에 확산
                  spread[nx][ny] += spreadAmount
					# 원래 칸에서는 빼주기
                  board[x][y] -= spreadAmount
  
  # 기존 맵에 확산된 양만큼 더해주기
  for x in range(r):
  	for y in range(c):
      	board[x][y] += spread[x][y]

3. 공기청정기 작동

처음에 노가다로 풀었는데.. 규칙을 찾으면 코드가 훨씬 간단하다.
우선 방향을 설정한다.

# 북, 동, 남, 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

나는 방향의 순서를 0 - 북, 1 - 동, 2 - 남, 3 - 서 로 정해주었다.

위쪽 순환 (반시계)
a. 반시계 방향 회전
: 반시계니까 동, 북, 서, 남 으로 순환돼야 한다.
초기 방향은 동쪽이니까dir = 1 로 선언하고
한칸씩 이동하다가 맵 끝에 다다르면
dir = (dir-1) % 4 으로 반시계로 회전한다.

b.바람 방향대로 한 칸씩 이동

board[x][y], tmp = tmp, board[x][y]

swap 을 이용하면 간단하게 두 변수를 바꿀 수 있다!

def clean_up():
	# 공기청정기 오른쪽 칸부터 시작
	x, y = air[0][0],1
    dir = 1
    tmp = 0
    
    while True:
    	nx = x + dx[dir]
        ny = y + dy[dir]
        
        # 반시계 회전
        if nx < 0 or nx >= r or ny < 0 or ny >= c:
        	dir = (dir-1) % 4
            continue
        
        # 공기청정기 좌표로 돌아오면 종료
        if x == air[0][0] and y == air[0][1]:
        	break
        
        board[x][y], tmp = tmp, board[x][y]
        x, y = nx, ny

아래쪽 순환 (시계)
a. 시계 방향 회전
: 방법은 동일하다. 동, 남, 서, 북 으로 순환돼야 한다.
맵 끝에 다다르면
dir = (dir+1) % 4 으로 방향을 바꿔주면 된다.
나머지 연산으로 회전하는 건 많이 사용되는 스킬이니 잘 알아두자!

b. 바람 방향대로 한 칸씩 이동
위랑 동일!

 def clean_down():
 	# 공기청정기 오른쪽 칸부터 시작
 	x, y = air[1][0],1
     dir = 1
     tmp = 0
     
     while True:
     	nx = x + dx[dir]
         ny = y + dy[dir]
         
         # 반시계 회전
         if nx < 0 or nx >= r or ny < 0 or ny >= c:
         	dir = (dir+1) % 4
             continue
         
         # 공기청정기 좌표로 돌아오면 종료
         if x == air[1][0] and y == air[1][1]:
         	break
         
         board[x][y], tmp = tmp, board[x][y]
         x, y = nx, ny