(백준) 17144번: 미세먼지 안녕! - 파이썬 풀이

<포스팅 요약>

1. 문제풀러가기

2. 문제 해결 코드

3. 로직 분석

---

1. 문제풀러가기

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

17144번: 미세먼지 안녕!

 

문제 해석:

1. 미세먼지를 확산시킨다.

아래와 왼쪽 그림과 같이 미세먼지가 분포되어 있다고 할때 ,

아래 오른쪽 그림과 같은 과정을 거친다.

 

2. 공기 청정기로 순환

 

 

---

2. 문제 해결 코드

**pypy로 돌려야됨

코드 (성공) 코드 정리 전

import sys
input = sys.stdin.readline

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

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

dx = [(0, -1), (0, 1), (1, 0), (-1, 0)]
topStartIdx = 0
bottomStartIdx = 0
for i in range(r):
    if arr[i][0] == -1:
        topStartIdx = i
        bottomStartIdx = i+1
        break


def clean():
    global arr
    arr_copy = [[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
                for a, b in dx:
                    nx = i+a
                    ny = j+b

                    if 0 <= nx < r and 0 <= ny < c and arr[nx][ny] != -1:
                        arr_copy[nx][ny] += arr[i][j]//5
                        cnt += 1

                arr_copy[i][j] = arr_copy[i][j] + \
                    arr[i][j]-(arr[i][j]//5*cnt)
            elif arr[i][j] == -1:
                arr_copy[i][j] = -1
    arr = arr_copy[:]


def activeTop():
    global arr, topStartIdx
    # top
    i = topStartIdx
    j = 0
    pre_num = 0

    while True:

        if i == topStartIdx and j != c-1:
            j += 1
        elif 0 < i <= topStartIdx and j == c-1:
            i -= 1
        elif i == 0 and j != 0:
            j -= 1
        elif 0 <= i < topStartIdx and j == 0:
            i += 1
        pre_num, arr[i][j] = arr[i][j], pre_num
        if i == topStartIdx and j == 0:
            arr[i][j] = -1
            break


def activeBottom():
    global arr, bottomStartIdx
    # bottom
    i = bottomStartIdx
    j = 0
    pre_num = 0
    while True:
        if i == bottomStartIdx and j != c-1:
            j += 1
        elif bottomStartIdx <= i < r-1 and j == c-1:
            i += 1
        elif i == r-1 and j != 0:
            j -= 1
        elif bottomStartIdx < i <= r-1 and j == 0:
            i -= 1

        pre_num, arr[i][j] = arr[i][j], pre_num
        if i == bottomStartIdx and j == 0:
            arr[i][j] = -1
            break


total = 0
for _ in range(t):
    clean()
    activeTop()
    activeBottom()


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

print(total)

 

위 코드에서 activeTop과 activeBottom 함수안 로직은 거의 노가다 이다 ㅋㅋㅋㅋㅋ

그래서 다른분들의 코드를 보면서, 조금 더 효율적인 로직으로 수정하였다.

동작하는 로직은 똑같지만, 훨씬 더 효율적이고 똑똑한 방법이다. 

 

앞으로 이런 동작은 아래 코드와 같은 로직으로 짜야 된다는 거를 배웠다 ^0^

 

코드 (성공) 코드 정리 후

import sys
input = sys.stdin.readline

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

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

dx = [(0, -1), (0, 1), (1, 0), (-1, 0)]
topStartIdx = 0
bottomStartIdx = 0
for i in range(r):
    if arr[i][0] == -1:
        topStartIdx = i
        bottomStartIdx = i+1
        break


def clean():
    global arr
    arr_copy = [[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
                for a, b in dx:
                    nx = i+a
                    ny = j+b

                    if 0 <= nx < r and 0 <= ny < c and arr[nx][ny] != -1:
                        arr_copy[nx][ny] += arr[i][j]//5
                        cnt += 1

                arr_copy[i][j] = arr_copy[i][j] + \
                    arr[i][j]-(arr[i][j]//5*cnt)
            elif arr[i][j] == -1:
                arr_copy[i][j] = -1
    arr = arr_copy[:]


def activeTop():
    global arr, topStartIdx
    dn = [(0, 1), (-1, 0), (0, -1), (1, 0)]
    pre_num = 0
    i = topStartIdx
    j = 0
    n = 0
    while True:
        dx = i+dn[n][0]
        dy = j+dn[n][1]
        if dx == topStartIdx and dy == 0:
            break
        if dx < 0 or dx > r-1 or dy < 0 or dy > c-1:
            n += 1
            continue
        pre_num, arr[dx][dy] = arr[dx][dy], pre_num
        i = dx
        j = dy


def activeBottom():
    global arr, bottomStartIdx
    dn = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    pre_num = 0
    i = bottomStartIdx
    j = 0
    n = 0
    while True:
        dx = i+dn[n][0]
        dy = j+dn[n][1]
        if dx == bottomStartIdx and dy == 0:
            break
        if dx < 0 or dx > r-1 or dy < 0 or dy > c-1:
            n += 1
            continue
        pre_num, arr[dx][dy] = arr[dx][dy], pre_num
        i = dx
        j = dy


total = 0
for _ in range(t):
    clean()
    activeTop()
    activeBottom()


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

print(total)

 

pypy로 안돌리면 시간초과뜬다 ㅜㅜ 

 

---

3. 로직분석

- clean 함수에 대해서

clean함수에서는 미세먼지를 확산시킨다.

1) 현재 위치에서 4방향으로 확산된 먼지를 0으로 초기화 되어 있는 arr_copy배열안에 넣어준다.

2) 현재위치 미세먼지도 조건에 따라 계산하여 배열에 넣어준다.

 

- activeTop과 activeBottom 함수에 대해서

1) activeTop은 공기청정기 윗쪽을 순환하는 로직

2) activeBottom은 공기청정기 아래쪽을 순환하는 로직

3) dx나 dy가 모서리에 닿으면 n+1을 하여 방향을 바꿔준다.