Gemstone's Devlog

[백준] 17144번: 미세먼지 안녕! (구현, 시뮬레이션) 본문

Data Structure & Algorithms

[백준] 17144번: 미세먼지 안녕! (구현, 시뮬레이션)

Gemstone 2022. 5. 4. 17:09

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

 

17144번: 미세먼지 안녕!

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사

www.acmicpc.net

 

교양시간에 수업은 안듣고 solved.ac Class4 문제들을 뒤적거리다가 재밌어 보여서 풀어봤던 문제였다.

구현 문제이기도 했고 문제가 복잡한 것 같아 효율성 따지지 않고 무지성으로 풀었는데, 역시 python3로 제출하니 시간초과가 났고, pypy3로 제출하니 겨우 통과하였다.

무지성 파이썬 코드

import sys
input = sys.stdin.readline
r, c, t = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(r)]
clean = []
def out_of_bounds(x, y):
    if x < 0 or x >= r or y < 0 or y >= c:
        return False
    if y == 0 and x in clean:
        return False
    return True
def spread():
    tmp = [[0 for _ in range(c)] for _ in range(r)]
    for i in range(r):
        for j in range(c):
            if arr[i][j] != 0 and arr[i][j] != -1:
                cnt = 0
                if out_of_bounds(i-1, j):
                    cnt += 1
                    tmp[i-1][j] += arr[i][j]//5
                if out_of_bounds(i+1, j):
                    cnt += 1
                    tmp[i+1][j] += arr[i][j]//5
                if out_of_bounds(i, j-1):
                    cnt += 1
                    tmp[i][j-1] += arr[i][j]//5
                if out_of_bounds(i, j+1):
                    cnt += 1
                    tmp[i][j+1] += arr[i][j]//5
                tmp[i][j] -= cnt*(arr[i][j]//5)
    for i in range(r):
        for j in range(c):
            arr[i][j] += tmp[i][j]
def wind():
    tmp = [[0 for _ in range(c)] for _ in range(r)]
    u, d = clean[0], clean[1]
    # 위 (반시계)
    for i in range(1, c-1):
        tmp[u][i+1] = arr[u][i]
        arr[u][i] = 0
    for i in range(1, u+1):
        tmp[u-i][c-1] = arr[u-i+1][c-1]
        arr[u - i + 1][c - 1] = 0
    for i in range(1, c):
        tmp[0][c-i-1] = arr[0][c-i]
        arr[0][c - i] = 0
    for i in range(1, u+1):
        if i != u:
            tmp[i][0] = arr[i - 1][0]
            arr[i - 1][0] = 0
        else:
            tmp[i][0] = 0
            arr[i - 1][0] = 0
    # 아래 (시계)
    for i in range(1, c-1):
        tmp[d][i+1] = arr[d][i]
        arr[d][i] = 0
    for i in range(1, r-d):
        tmp[d+i][c-1] = arr[d+i-1][c-1]
        arr[d + i - 1][c - 1] = 0
    for i in range(1, c):
        tmp[r-1][c-i-1] = arr[r-1][c-i]
        arr[r - 1][c - i] = 0
    for i in range(1, r-d):
        if i != r-d-1:
            tmp[r - 1 - i][0] = arr[r - i][0]
            arr[r - i][0] = 0
        else:
            tmp[r-1-i][0] = 0
            arr[r - i][0] = 0

    for i in range(r):
        for j in range(c):
            arr[i][j] += tmp[i][j]
for i in range(r):
    if arr[i][0] == -1:
        clean.append(i)
for _ in range(t):
    spread()
    wind()
ans = 0
for i in range(r):
    for j in range(c):
        ans += arr[i][j]
print(ans+2)

 

하지만 이렇게 풀어보니 코드의 가독성도 떨어지고 알고리즘이 매우 비효율적이라는 것을 알 수 있다. 

문제를 풀면서 생각난 부분인데, 어차피 구하고자 하는 답은 미세먼지의 총 양이고, 공기청정기 바람이 불 때 그 미세먼지들이 어떻게 이동하는지가 중요하기보다는 공기청정기 바로 근처에 있는 미세먼지가 공기청정기 안으로 들어가냐 아니면 안들어가냐 이 부분만 따지면 될 듯 했다. 

 

우선 가독성이 조금 더 좋은 다른 분들의 코드를 참고해보았다.

이 코드 역시 pypy3로 제출해야지만 통과하지만 가독성이 내가 쓴 코드보다 더 읽기 좋았다.

 

 

가독성 좋은 코드

import sys

input = sys.stdin.readline

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

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

up = -1
down = -1
# 공기 청정기 위치 찾기
for i in range(r):
    if arr[i][0] == -1:
        up = i
        down = i + 1
        break

# 미세먼지 확산
def spread():
    dx = [-1, 0, 0, 1]
    dy = [0, -1, 1, 0]

    tmp_arr = [[0] * c for _ in range(r)]
    for i in range(r):
        for j in range(c):
            if arr[i][j] != 0 and arr[i][j] != -1:
                tmp = 0
                for k in range(4):
                    nx = dx[k] + i
                    ny = dy[k] + j
                    if 0 <= nx < r and 0 <= ny < c and arr[nx][ny] != -1:
                        tmp_arr[nx][ny] += arr[i][j] // 5
                        tmp += arr[i][j] // 5
                arr[i][j] -= tmp

    for i in range(r):
        for j in range(c):
            arr[i][j] += tmp_arr[i][j]

# 공기청정기 위쪽 이동
def air_up():
    dx = [0, -1, 0, 1]
    dy = [1, 0, -1, 0]
    direct = 0
    before = 0
    x, y = up, 1
    while True:
        nx = x + dx[direct]
        ny = y + dy[direct]
        if x == up and y == 0:
            break
        if nx < 0 or nx >= r or ny < 0 or ny >= c:
            direct += 1
            continue
        arr[x][y], before = before, arr[x][y]
        x = nx
        y = ny

# 공기청정기 아래쪽 이동
def air_down():
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    direct = 0
    before = 0
    x, y = down, 1
    while True:
        nx = x + dx[direct]
        ny = y + dy[direct]
        if x == down and y == 0:
            break
        if nx < 0 or nx >= r or ny < 0 or ny >= c:
            direct += 1
            continue
        arr[x][y], before = before, arr[x][y]
        x = nx
        y = ny


for _ in range(t):
    spread()
    air_up()
    air_down()

answer = 0
for i in range(r):
    for j in range(c):
        if arr[i][j] > 0:
            answer += arr[i][j]

print(answer)