[백준/Python] 17144번 미세먼지 안녕!

삼성 SW 역량 테스트 기출 문제

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

17144번: 미세먼지 안녕!

---

---

Solution

	from collections import deque
	import copy
	def munji(m, k):
	after_munji = copy.deepcopy(m)
	if k == t:
	ans = 0
	for i in range(r):
	ans += sum(after_munji[i])
	print(ans+2)
	return
	q = deque()
	for i in range(r):
	for j in range(c):
	if m[i][j] > 0:
	q.append((i,j))
	while q:
	y, x = q.popleft()
	cnt = 0
	for dx, dy in (-1,0),(1,0),(0,-1),(0,1):
	nx, ny = x+dx, y+dy
	if nx < 0 or nx >= c or ny < 0 or ny >= r:
	continue
	if m[ny][nx] != -1:
	after_munji[ny][nx] += m[y][x]//5
	cnt += 1
	after_munji[y][x] -= ((m[y][x]//5) * cnt)
	cn = []
	for i in range(r):
	if m[i][0] == -1:
	cn.append(i)
	tmp = [after_munji[cn[0]][1]]
	after_munji[cn[0]][1] = 0
	for i in range(2,c-1):
	tmp.append(after_munji[cn[0]][i])
	after_munji[cn[0]][i] = tmp.pop(0)
	for i in range(cn[0], -1, -1):
	tmp.append(after_munji[i][c-1])
	after_munji[i][c-1] = tmp.pop(0)
	for i in range(c-2, -1, -1):
	tmp.append(after_munji[0][i])
	after_munji[0][i] = tmp.pop(0)
	for i in range(1, cn[0]):
	tmp.append(after_munji[i][0])
	after_munji[i][0] = tmp.pop(0)
	tmp = [after_munji[cn[1]][1]]
	after_munji[cn[1]][1] = 0
	for i in range(2,c-1):
	tmp.append(after_munji[cn[1]][i])
	after_munji[cn[1]][i] = tmp.pop(0)
	for i in range(cn[1], r):
	tmp.append(after_munji[i][c-1])
	after_munji[i][c-1] = tmp.pop(0)
	for i in range(c-2, -1, -1):
	tmp.append(after_munji[r-1][i])
	after_munji[r-1][i] = tmp.pop(0)
	for i in range(r-2, cn[1], -1):
	tmp.append(after_munji[i][0])
	after_munji[i][0] = tmp.pop(0)
	munji(after_munji,k+1)
	r, c, t = map(int, input().split(' '))
	maps = [list(map(int, input().split(' '))) for _ in range(r)]
	after_munji = copy.deepcopy(maps)
	munji(maps,0)

view raw 미세먼지안녕!.py hosted with ❤ by GitHub

 

문제 유형 : 시뮬레이션, BFS/DFS

 

삼성에는 유독 이런 시뮬레이션 문제가 많은 것 같다.

많은 건 좋지만 내가 좀 어려워하는 경향이 있어서 그게 문제다.

쉽게 말해서 나와있는 문제의 조건들을 구현만 하면 되는 건데 왜 이렇게 까다로운지 모르겠다.

이게 정답률 54%라니 역시 코딩 잘하는 사람이 너무 많다.

 

구현해야할 것은 크게 두 개.

1. 미세먼지 확산

      미세먼지가 확산하는 것은 BFS로 구현했다.

      미세먼지가 있는 칸을 큐에 담고 공기 청정기가 있는 인덱스가 아니면 확산시킨다. 

 

2. 공기청정기 작동

     공기청정기가 특이하게 작동해서 좀 골치아팠다.

     미세먼지를 한 칸씩 밀면서 가로, 세로에 겹치는 칸들이 있어서 주의하면서 구현했다.

 

초마다 1, 2가 순서대로 일어나므로 T초 뒤의 미세먼지 양을 출력.

 

성공 ^_^