[백준/파이썬] 17144번 미세먼지 안녕! 풀이
업데이트:
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 17144번 미세먼지 안녕!
- 문제풀이 코드 GitHub 링크
- 제출 언어: PyPy3
풀이
문제
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 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초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.
- 자세한 문제 및 입출력 예제는 상단의 문제 출처(백준 홈페이지)를 참조해주세요
코드
import sys; read = sys.stdin.readline
r, c, t = map(int, read().split())
ap = []
a = []
for i in range(r):
a.append(list(map(int, read().split())))
if a[-1][0] == -1:
ap.append(i)
a[-1][0] = 0
for dt in range(t):
na = [[0]*c for _ in range(r)]
for i in range(r):
for j in range(c):
if a[i][j] > 0:
na[i][j] += a[i][j]
if i > 0 and (i - 1 not in ap or j > 0):
na[i - 1][j] += a[i][j] // 5
na[i][j] -= a[i][j] // 5
if i < r - 1 and (i + 1 not in ap or j > 0):
na[i + 1][j] += a[i][j] // 5
na[i][j] -= a[i][j] // 5
if j > 0 and (i not in ap or j - 1 > 0):
na[i][j - 1] += a[i][j] // 5
na[i][j] -= a[i][j] // 5
if j < c - 1:
na[i][j + 1] += a[i][j] // 5
na[i][j] -= a[i][j] // 5
a = na
for i in range(ap[0] - 1, 0, -1): a[i][0] = a[i - 1][0]
for j in range(c - 1): a[0][j] = a[0][j + 1]
for i in range(ap[0]): a[i][c - 1] = a[i + 1][c - 1]
for j in range(c - 1, 1, -1): a[ap[0]][j] = a[ap[0]][j - 1]
a[ap[0]][1] = 0
for i in range(ap[1] + 1, r - 1): a[i][0] = a[i + 1][0]
for j in range(c - 1): a[r - 1][j] = a[r - 1][j + 1]
for i in range(r - 1, ap[1], -1): a[i][c - 1] = a[i - 1][c - 1]
for j in range(c - 1, 1, -1): a[ap[1]][j] = a[ap[1]][j - 1]
a[ap[1]][1] = 0
print(sum(map(lambda x: sum(x), a)))
설명
이번 문제는 Python3로 시간초과가 발생하여 PyPy3로 제출하였습니다. Python3도 제출자가 상당수 있는 것을 보면 단순 제 코드의 비효율성으로 인한 것으로 사료됩니다만, 개괄적인 시간복잡도 Big-O는 같을 것입니다.
기본적으로 시뮬레이션이기 때문에, 구현에 있어 헷갈리는 부분은 있어도 쉬운 문제입니다.
문제의 조건대로 확산 -> 공기 청정기 동작 -> 확산 -> 동작 -> … 반복입니다
확산 단계에서 주의할 점은, a[i][j]에서 확산된 공기는 a[i+1][j] 등 인접칸의 확산 단계에서 고려해서는 안된다는 것입니다. 즉, 2차원 리스트 하나만 써서 누산하는 방법으로는 해결하기가 어렵습니다. 모두 동시에 처리하지 않는 한, 확산하는 양을 구할 때 같이 계산되어 버릴 것입니다.
이를 방지하기 위해, 임시로 같은 크기의 2차원 리스트를 만들어, 확산한 공기, 확산하고 남은 공기만 누산시킵니다. 다만, 같은 크기의 리스트를 생성하는 데 또 r*c 의 시간이 걸리므로, 아마 Python3로 제출해서 시간 초과가 나는 이유가 이것으로 생각됩니다. 다른 방법을 사용한다면 아마 Python3로도 통과하지 않을까 싶습니다.
확산 단계가 끝나면, 공기 청정기의 동작 단계입니다.
이 부분은 딱히 설명까지 필요해보이진 않습니다. 인덱스의 시작과 끝을 헷갈리실 수 있는 점 유의해주세요.
위 단계들을 t번 반복한 후, 각 리스트의 합을 모두 더해 최종적인 합을 출력하였습니다.
댓글남기기