[백준] 17144 미세먼지 안녕! python 풀이

문제

• 난이도: 골드4
• 알고리즘 분류: 구현, 시뮬레이션
• 요약: T초 동안 미세먼지가 확산되고 공기청정기가 작동될 때, 남아있는 미세먼지 양 출력하기

 

풀이

미세먼지 확산

1. 미세먼지가 확산되어 변화할 값을 저장하는 배열 생성
board 배열에 바로 변화할 값을 추가할 경우, 이전의 변화된 값이 다음 진행에 영향을 끼침 -> 안 됨

2. 인접한 네 방향으로 확산
변화할 미세먼지 배열 업데이트 (dust)
확산된 미세먼지 양 업데이트 (spread_amount)

3. 해당 위치에서 확산된 미세먼지 양만큼 제거

 

 

공기청정기 작동

ex) 아래쪽 공기청정기 작동 방식

• 시계방향으로 순환 (동 남 북 서)
• 바람이 불면 미세먼지가 바람의 방향대로 한 칸씩 이동
• 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화됨

1. 공기청정기 좌표에서 오른쪽으로 한 칸 이동한 값을 시작점으로 설정
2. 기존 공기청정기 좌표로 돌아왔을 경우, 무한루프 종료
3. (동 남 북 서) 방향으로 이동하는데, 좌표 값이 주어진 R과 C 범위를 벗어났을 때 방향 전환으로 간주하고 dir += 1 처리
4. 해당 방향으로 이동할 때, 현재 위치의 값과 이전 값을 swap 방식을 사용하여 처리

 

코드

import sys

input = sys.stdin.readline

r, c, t = map(int, input().split())

board = []
for _ in range(r):
	board.append(list(map(int, input().split())))

# 공기청정기 위치 구하기
for i in range(r):
	if board[i][0] == -1:
		cleaner_top = i
		cleaner_down = i + 1
		break

def dust_spread():
	#     동  북  서  남
	dx = [-1, 0, 1, 0]
	dy = [0, -1, 0, 1]

	dust = [[0] * c for _ in range(r)]

	for y in range(r):
		for x in range(c):
			if board[y][x] > 0:
				spread_amount = 0

				# 네 방향으로 확산
				for i in range(4):
					nx = x + dx[i]
					ny = y + dy[i]

					if 0 <= ny < r and 0 <= nx < c:
						if board[ny][nx] != -1:
							dust[ny][nx] += board[y][x] // 5
							spread_amount += board[y][x] // 5
				
				board[y][x] -= spread_amount
	
	for y in range(r):
		for x in range(c):
			board[y][x] += dust[y][x]

def top_rotate():
	#     동  북  서  남
	dx = [1, 0, -1, 0]
	dy = [0, -1, 0, 1]

	dir = 0
	prev = 0
	y, x = cleaner_top, 1

	while True:
		if y == cleaner_top and x == 0:
			break

		nx = x + dx[dir]
		ny = y + dy[dir]

		if not(0 <= ny < r and 0 <= nx < c):
			dir += 1
			continue
		
		board[y][x], prev = prev, board[y][x]
		y, x = ny, nx

def down_rotate():
	#     동  남  서  북
	dx = [1, 0, -1, 0]
	dy = [0, 1, 0, -1]

	dir = 0
	prev = 0
	y, x = cleaner_down, 1

	while True:
		if y == cleaner_down and x == 0:
			break

		nx = x + dx[dir]
		ny = y + dy[dir]

		if not(0 <= ny < r and 0 <= nx < c):
			dir += 1
			continue
		
		board[y][x], prev = prev, board[y][x]
		y, x = ny, nx

for _ in range(t):
	dust_spread()
	top_rotate()
	down_rotate()

amount = 0
for i in range(r):
	for j in range(c):
		if board[i][j] > 0: # 공기청정기 값 제외
			amount += board[i][j]
print(amount)