[Python] BOJ 17144 - 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

# 2019년 상반기 삼성 SW 역량테스트 문제이다.

# 역시 삼성답게 엄청난 끈기와 인내력을 필요로 하는 빡구현+시뮬레이션 문제였다..

 

# 우선 T초동안 시뮬레이션을 돌려야하니 while T를 해준다

   시뮬레이션을 돌리는 매 초마다 각각 새로 먼지위치, 먼지 양을 구해야 하므로 

   매 초마다 먼지 위치를 저장하는 dust와 공기청정기 위치를 저장하는 clean을 초기화해준다.

   (공기청정기는 움직이지 않으므로 사실 고정시켜도 된다.) -> 시간 약간(?) 줄일 수 있을 듯

   확산되는 먼지의 양을 저장하는 dic도 초기화해준다.

 

# 이제 먼지를 확산시킨다!

   1. (0, 0)부터 (R-1, C-1)까지 돌며 먼지 위치를 dust에 저장하고, 공기청정기 위치를 clean에 저장한다.

      * (nx, ny) = 다음으로 탐색할 위치

 

   2. 모든 먼지 위치를 돌며 각각의 상하좌우칸이 벽이 아니고 공기청정기가 아니라면 (21번째 줄)

        cnt 1증가

 

   3-1. m[nx][ny]가 0이라면 그 자리에 바로 int(m[i][j] / 5)를 넣어준다.

         (확산되는 양은 A_r,c / 5이고 소수점은 버리므로 m[i][j]를 5로 나눈값에 int를 씌워서 소수점을 버린다.)

   3-2. m[nx][ny]에 이미 먼지가 존재한다면(0이 아니라면) 우선 dic[(nx, ny)]에 int(m[i][j] / 5)를 더해준다.

   

   4. 상하좌우칸을 탐색완료했으면 m[i][j]에서 확산된 먼지의 양인 int(m[i][j] / 5) * cnt 를 빼준다.

 

   5. 모든 먼지 칸에서 확산되는 먼지를 다 빼 준 뒤,

       각 인접한 칸에서 확산되어야 할 먼지 양인 dic[(nx, ny)]를 m[i][j]에 넣어준다.

 

    * 중요!

       (5번에서 마지막에 넣어주는 이유는 다음 칸이 원래 먼지양이 4여서 확산되는 먼지가 없는데, 

       옆 칸에서 1이상의 먼지가 넘어오는 것을 즉시 더해주면 5이상이 되어서 확산되는 먼지가 생긴다.

       실제로는 먼지 확산이 동시에 일어나기 때문에 옆 칸으로 가야하는 먼지들을 dic에 저장해놓았다가

       모두 확산시킨 후(빼주는 것만 우선) 마지막에 dic에 있는 먼지 양을 그 칸에 더해줘야 한다.)

 

 

# 먼지 확산이 완료되었으면, 이제 공기청정기를 작동시킨다.

   공기청정기 위쪽은 반시계, 아래쪽은 시계방향으로 회전하므로 두가지로 나누어서 코드를 짰다.

   (위쪽 = 32 ~ 51줄, 아래쪽 = 54 ~ 72줄) (i = 공기청정기 위쪽 좌표, j: 공기청정기 아래쪽 좌표)

  

   # 공기청정기 작동하는 코드는 프로그래머스의 '행렬 테두리 회전하기'문제와 똑같이 돌리면 된다.

      (자세한 건 직접 손으로 돌려가며 코드랑 비교해보면 바로 이해가 된다.)

      공기청정기에서 나오는 칸인 m[i][1]과 m[j][1]은 무조건 0이다.

      또한, 공기청정기로 들어가는 m[i-1][0]과 m[j+1][0]칸은 제외하고 돌렸다. (어차피 사라지므로)

 

# 공기청정기도 작동을 완료시켰으면, m의 모든 칸을 탐색하며

   m[i][j]가 0보다 크면 dab에 먼지 양을 더해주고 dab을 출력하면 끝!

   (공기청정기가 있는 칸은 -1이고, 먼지가 없는 칸은 0이다.)

 

from collections import defaultdict, deque
import sys
input = sys.stdin.readline
R,C,T = map(int,input().split())
m = [list(map(int,input().split())) for _ in range(R)]
dx, dy = [-1,1,0,0], [0,0,-1,1]
while T:
	dust, clean = [], []
	## 먼지 확산
	dic = defaultdict(int)
	for i in range(R):
		for j in range(C):
			if m[i][j] > 0:
				dust.append([i, j])
			elif m[i][j] == -1:
				clean.append(i)
	for i, j in dust:
		cnt = 0
		for k in range(4):
			nx, ny = i + dx[k], j + dy[k]
			if 0 <= nx < R and 0 <= ny < C and m[nx][ny] != -1:
				cnt += 1
				if not m[nx][ny]:
					m[nx][ny] = int(m[i][j] / 5)
				else:
					dic[(nx, ny)] += int(m[i][j] / 5)
		m[i][j] = m[i][j] - int(m[i][j] / 5) * cnt
	for i, j in dic:
		m[i][j] += dic[(i, j)]
	
	## 공기청정기 작동(반시계방향)
	i, j = clean[0], clean[1]
	tmp1 = m[i][C-1]
	# 우
	for y in range(C-1, 1, -1):
		m[i][y] = m[i][y-1]
	m[i][1] = 0
	tmp2 = m[0][C-1]
	# 상
	for x in range(0, i-1):
		m[x][C-1] = m[x+1][C-1]
	m[i-1][C-1] = tmp1
	tmp1 = m[0][0]
	# 좌
	for y in range(C-2):
		m[0][y] = m[0][y+1]
	m[0][C-2] = tmp2
	# 하
	for x in range(i-1, 1, -1):
		m[x][0] = m[x-1][0]
	m[1][0] = tmp1

	## 시계방향
	tmp1 = m[j][C-1]
	# 우
	for y in range(C-1, 1, -1):
		m[j][y] = m[j][y-1]
	m[j][1] = 0
	tmp2 = m[R-1][C-1]
	# 하
	for x in range(R-1, j+1, -1):
		m[x][C-1] = m[x-1][C-1]
	m[j+1][C-1] = tmp1
	tmp1 = m[R-1][0]
	# 좌
	for y in range(C-2):
		m[R-1][y] = m[R-1][y+1]
	m[R-1][C-2] = tmp2
	# 상
	for x in range(j+1, R-2):
		m[x][0] = m[x+1][0]
	m[R-2][0] = tmp1

	T -= 1

dab = 0
for i in range(R):
	for j in range(C):
		if m[i][j] > 0:
			dab += m[i][j]
print(dab)

(solved.ac 티어: 골드 5)

 

# 4월에 한번 1시간정도 걸려 풀어봤는데, 틀려가지고 멘탈나가서 손 놓고 있다가 오늘 다시 멘탈잡고 풀었다..

  공기청정기를 작동하는 코드가 문제여서 다시 짰다.

  (처음엔 상 하 좌 우로 돌려야 하는 원소들을 deque에 저장한 뒤, deque.rotate로 직접 돌리고 

   다시 m배열에 복사하는 식으로 짰다.)

 

# 확실히 구현, 시뮬문제가 디버깅을 할 수 없어서(할 수는 있지만, 직접 먼지 확산되는 과정과

   공기청정기를 돌리는 과정을 매 초마다 손으로 다 해보면서 비교하려면 코드짜는 것만큼의 힘과

   시간이 소요된다.) 1시간걸려 풀고 틀리면 멘탈이 무너진다.

   이럴 땐, 잠시 쉬었다가 며칠지나거나 몇 달지나서 다시 처음부터 푸는 게 도움이 된다!

 

# '상어 초등학교' 문제랑 이 문제처럼 1시간정도 걸려 풀고 맞추면 기분이 엄청좋다 ㅋㅋ