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

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

17144번: 미세먼지 안녕!

아이디어

• 첫 미세먼지의 좌표와 공기 청정기의 좌표를 미리 저장해 둔다.
• bfs에서 상요한 큐를 이용해 미세먼지를 확산시킨다.
• 확산된 배열을 복사해서 저장
• 공기청정기를 작동 위아래 별개로 구현
• 원하는 만큼 반복은 bfs인자로 t를 넘겨 한 번 확산 청정을 실행할 때마다 -1
• t가 0이 되면 미세먼지의 양을 sum을 통해 구해 출력

구현(메모리, 시간 모두 최악)

import sys
input = sys.stdin.readline

dy = [0, -1, 0, 1]
dx = [-1, 0, 1, 0]

from collections import deque
import copy
def dfs(li_real, dust, t):
    if t == 0:
        result = 0
        for i in li_real:
            result += sum(i)
        print(result+2)
        return
    q = deque(dust)
    li_tmp = copy.copy(li_real)
    dust_tmp = []
    # 미세먼지 확산
    while q:
        y, x = q.pop()
        cnt = 0
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0<=ny<r and 0<=nx<c and li_real[ny][nx] != -1:
                cnt += 1
                li_tmp[ny][nx] += (li_real[y][x]//5)
                dust_tmp.append((ny,nx))
        li_tmp[y][x] -= (li_real[y][x]//5*cnt)
    # 공기청정기 작동

    # 위쪽
    y, x = cleaner[0]
    for i in range(y-1, 0, -1):
        li_tmp[i][0] = li_tmp[i-1][0]
    for i in range(c-1):
        li_tmp[0][i] = li_tmp[0][i+1]
    for i in range(0, y):
        li_tmp[i][c-1] = li_tmp[i+1][c-1]
    for i in range(c-1, 0, -1):
        li_tmp[y][i] =  li_tmp[y][i-1]
    li_tmp[y][x+1] = 0

    #아래쪽
    y, x = cleaner[1]
    for i in range(y+1, r-1):
        li_tmp[i][0] = li_tmp[i+1][0]
    for i in range(c-1):
        li_tmp[r-1][i] = li_tmp[r-1][i+1]
    for i in range(r-1, y, -1):
        li_tmp[i][c-1] = li_tmp[i-1][c-1]
    for i in range(c-1, 0, -1):
        li_tmp[y][i] =  li_tmp[y][i-1]
    li_tmp[y][x+1] = 0

    dfs(li_tmp, dust_tmp, t-1)
            


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

# 처음 미세먼지 위치와 공기청정기 위치 리스트 생성
dust = []
cleaner = []
for i in range(r):
    for j in range(c):
        if li[i][j] > 0:
            dust.append((i,j))
        if li[i][j] == -1:
            cleaner.append((i,j))


dfs(li, dust, t)

되긴 한다 다만 너무너무 느리다 메모리도 너무 잡아먹는다...

 

개선 방안 (GPT)

gpt한테 이 코들가 왜 안 좋은 코드인지 물어봤다...

 

이 코드가 안 좋은 코드로 여겨지는 몇 가지 이유가 있습니다. 아래에서 자세히 설명하겠습니다.

1. 코드 가독성 부족:
   - 변수 이름: 변수 이름이 간결하지 않고 의미를 파악하기 어렵습니다. 예를 들어, `li_real`, `li_tmp`, `dust_tmp` 등의 변수 이름은 코드를 읽을 때 혼동을 줄 수 있습니다.
   - 마찬가지로, `dfs` 함수의 매개변수들과 함수의 역할이 명확하게 주석으로 설명되지 않아 코드를 이해하기 어렵게 만듭니다.

2. 불필요한 모듈 및 복사:
   - `import copy`를 사용하고 `copy.copy`를 통해 리스트를 복사하는 대신, 리스트를 복사하는 대신 직접 리스트를 조작하는 방식으로 코드를 간소화할 수 있습니다.
   - 또한 `collections` 모듈에서 `deque`를 사용하는 것은 큐를 활용할 때 유용하지만, 이 코드에서는 리스트로 충분히 대체할 수 있습니다.

3. 불필요한 전역 변수 사용:
   - `dy`와 `dx`는 전역 변수로 정의되어 있지만, 이 변수들은 `dfs` 함수 내에서만 사용되므로 함수 내부로 이동하여 지역 변수로 선언하는 것이 더 좋습니다.

4. 코드 중복:
   - 공기 청정기 작동 부분에서 코드가 중복되고, 이로 인해 유지보수가 어려워집니다. 이러한 부분을 함수로 추상화하면 코드의 가독성을 향상시킬 수 있습니다.

5. 재귀 호출 제한:
   - 이 코드는 재귀 함수로 구현되어 있으며, 입력 크기가 큰 경우에는 재귀 호출 제한에 도달할 수 있습니다. 이를 해결하기 위해 반복문을 사용하거나 재귀 깊이를 제한하는 방법을 고려해야 합니다.

이러한 이유로 코드를 리팩토링하고 가독성을 높이는 작업이 필요합니다. 함수의 역할을 명확히 설명하고, 변수 이름을 의미있게 지정하며, 중복 코드를 제거하고 모듈 및 라이브러리의 적절한 사용을 고려하여 코드를 개선해야 합니다.

gpt가 코드를 왜 이따구로 짰냐고 혼내는 것 같다,,, 

 

그래서 그럼 너가 짜봐 얼마나 잘 짜는지 보자고! 

그렇게 gpt가 내게 보내온 코드

import sys
input = sys.stdin.readline

def spread_dust(matrix):
    new_matrix = [[0] * C for _ in range(R)]
    
    for r in range(R):
        for c in range(C):
            if matrix[r][c] > 0:
                spread_amount = matrix[r][c] // 5
                for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < R and 0 <= nc < C and matrix[nr][nc] != -1:
                        new_matrix[nr][nc] += spread_amount
                        matrix[r][c] -= spread_amount
    
    for r in range(R):
        for c in range(C):
            matrix[r][c] += new_matrix[r][c]

def operate_air_purifier(matrix, air_purifier):
    upper_cleaner, lower_cleaner = air_purifier
    upper_cleaner_row = upper_cleaner[0]
    lower_cleaner_row = lower_cleaner[0]
    
    # Upper air purifier
    for r in range(upper_cleaner_row - 1, 0, -1):
        matrix[r][0] = matrix[r - 1][0]
    for c in range(C - 1):
        matrix[0][c] = matrix[0][c + 1]
    for r in range(upper_cleaner_row):
        matrix[r][C - 1] = matrix[r + 1][C - 1]
    for c in range(C - 1, 0, -1):
        matrix[upper_cleaner_row][c] = matrix[upper_cleaner_row][c - 1]
    matrix[upper_cleaner_row][1] = 0
    
    # Lower air purifier
    for r in range(lower_cleaner_row + 1, R - 1):
        matrix[r][0] = matrix[r + 1][0]
    for c in range(C - 1):
        matrix[R - 1][c] = matrix[R - 1][c + 1]
    for r in range(R - 1, lower_cleaner_row, -1):
        matrix[r][C - 1] = matrix[r - 1][C - 1]
    for c in range(C - 1, 0, -1):
        matrix[lower_cleaner_row][c] = matrix[lower_cleaner_row][c - 1]
    matrix[lower_cleaner_row][1] = 0

def total_dust_amount(matrix):
    total = 0
    for row in matrix:
        total += sum(row)
    return total + 2

R, C, T = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(R)]

air_purifier = []
for r in range(R):
    if matrix[r][0] == -1:
        air_purifier.append((r, 0))

for _ in range(T):
    spread_dust(matrix)
    operate_air_purifier(matrix, air_purifier)

result = total_dust_amount(matrix)
print(result)

너무 깔끔하다..

간단히 설명해 주면

• 여기서는 그냥 먼지 확산 함수와 공기청정기 함수를 만들어 두 함수를 T번 반복하는 식으로 했다..
• 공기확산을 진행하는 방법에서 내 코드와 많이 차이가 난다.
• R과 C가 너무 작아 미리 먼지의 위치를 파악하지 않아도 된다. 확산 함수 내에서 그냥 2중 for문을 돌며 먼지인지 확인하고 먼지면 상하좌우로 확산을 시작한다.
• 더하는 값은 새로운 리스트에 저장하고 확산 후 줄어드는 값은 원본 리스트에서 바로 빼줬다.
• 반복문이 끝나면 새로운 리스트와 원본 리스트를 합쳐 확산을 마무리한다.
• 이후 확산된 리스트를 가지고 공기청정기를 돌리는 함수를 실행. 이 함수는 그냥 원시코딩이다.
• T만큼의 확산 청정이 완료되면 총 먼지량을 구하는 함수를 실행시켜 답을 구한다.

마무리

• gpt가 해준 충고를 꼭 기억하자
• 코드 가독성 부족 - 이건 어떻게 해야 하지 이 문제에 대한 부분은 따로 글을 적어봐야겠다.
• 불필요한 모듈 및 복사 - 필요한 것만 쓰자... 이게 제일 어려운 듯
• 코드 중복 - 반복적으로 사용되는 값은 변수로 따로 저장해서 쓰자
• 재귀 호출 제한 - 입력의 크기가 크면 이 부분을 고려하자