구현 진짜 힘들다.... (#17144 미세먼지 안녕!)

#17144 미세먼지 안녕! https://www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

토요일에 시도했다가 포기하고 죽어있었다.

 

뭔가 잘못 구현한 부분이 있었는데 눈에 보이지 않았기 때문이다.

 

하지만 해결해냈다.

 

문제는 다음과 같았다.

 

먼지 데이터를 조금 더 효율적으로 관리하고 싶었다.

그래서 먼지의 위치를 저장한 리스트를 만들었었는데

공기청정기가 작동하게되면 먼지의 위치가 바뀐다.

이걸 반영을 안해줬기 때문에 문제가 발생했다.

 

 

이걸 파악한 뒤, 먼지의 확산 - 이동이 발생하기 전에 먼지의 위치를 별도로 파악했다.

하지만 이렇게 변경함으로 인해서 효율성은 훨씬 떨어졌다.

 

sys.stdin.readline, deque를 적용한 뒤, 채점 언어를 pypy3로 변경하고서야 겨우 통과했다.

 

구현은 너무나 힘든 것 같다 ㅜㅜ

import sys
from collections import deque

input = sys.stdin.readline

#### 입력 받을 변수 정의하기
# 지도 정보 저장
maps = []
# 공기청정기 정보 저장
cleaner = []

#### 입력받기
r, c, t = map(int, input().split())
# 지도 정보 입력받기
for y in range(r):
    row = input().split()
    for x in range(c):
        tmp = int(row[x])
        if tmp == -1:  # is cleaner
            cleaner.append([y, x])
        row[x] = tmp
    maps.append(row)

# for m in maps:
#     print(m)

# print("cleaner : ", cleaner)


#### 필요한 함수 미리 저장하기
# 올바른 좌표인지 확인하기
def valid_pos(y, x):
    if 0 <= y < r and 0 <= x < c:  # 올바른 칸인가?
        if maps[y][x] != -1:  # 공기청정기가 아닌가?
            return True
    return False


# 먼지 저장 리스트

#### 실행하기 (여기부터 t 회 만큼 실행되어야한다.)
while t:
    t -= 1
    # 먼지 찾기
    dusts = deque()  # [y, x]
    for y in range(r):
        for x in range(c):
            if maps[y][x] > 0:
                dusts.append([y, x])

    # 이동하는 먼지 정보 저장. -> 한번에 적용하기
    move_dusts = deque()  # [y, x, amount] 이렇게 저장하기

    ### 1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
    # 움직이는 방향

    ## (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
    moves = [[-1, 0], [1, 0], [0, 1], [0, -1]]
    while dusts:
        y, x = dusts.popleft()
        amount = maps[y][x]
        ## 확산되는 양은 Ar,c/5이고 소수점은 버린다. 즉, ⌊Ar,c/5⌋이다.
        move_amount = amount // 5
        if move_amount > 0:
            cnt = 0
            for my, mx in moves:
                ny, nx = y + my, x + mx
                ## 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
                if valid_pos(ny, nx):
                    # 이동 정보 저장
                    move_dusts.append([ny, nx, move_amount])
                    cnt += 1
        ## (r, c)에 남은 미세먼지의 양은 Ar,c - ⌊Ar,c/5⌋×(확산된 방향의 개수) 이다.
        amount -= move_amount * cnt
        maps[y][x] = amount
    ## 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
    while move_dusts:
        y, x, amount = move_dusts.popleft()
        maps[y][x] += amount

    # print("확산 후 : ")
    # for m in maps:
    #     print(m)

    ### 2. 공기청정기가 작동한다. 공기청정기에서는 바람이 나온다.
    ## 위쪽 공기청정기의 바람은 반시계방향으로 순환하고
    u_y, u_x = cleaner[0]
    prev = 0  # 공기청정기에서 나오는 바람은 먼지가 없다.
    # 오른쪽 이동
    for x in range(u_x + 1, c):
        now = maps[u_y][x]
        maps[u_y][x] = prev
        prev = now
    # 맨 오른쪽 칸에서에서 위쪽 이동
    for y in range(u_y - 1, -1, -1):
        now = maps[y][c - 1]
        maps[y][c - 1] = prev
        prev = now
    # 맨 오른쪽 맨 위에서 왼쪽 이동
    for x in range(c - 2, -1, -1):
        now = maps[0][x]
        maps[0][x] = prev
        prev = now
    # 맨 왼쪽 위에서 아래쪽 이동
    for y in range(1, u_y):
        now = maps[y][u_x]
        maps[y][u_x] = prev
        prev = now

    ## 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
    d_y, d_x = cleaner[1]
    prev = 0  # 공기청정기에서 나오는 바람은 먼지가 없다.
    # 오른쪽 이동
    for x in range(d_x + 1, c):  # 인덱스 맞는지 확인하기
        now = maps[d_y][x]
        maps[d_y][x] = prev
        prev = now
    # 맨 오른쪽 칸에서 아래 이동
    for y in range(d_y + 1, r):
        now = maps[y][c - 1]
        maps[y][c - 1] = prev
        prev = now
    # 맨 오른쪽 아래에서 왼쪽 이동
    for x in range(c - 2, -1, -1):
        now = maps[r - 1][x]
        maps[r - 1][x] = prev
        prev = now
    # 맨 왼쪽 아래에서 위쪽 이동
    for y in range(r - 2, d_y, -1):
        now = maps[y][d_x]
        maps[y][d_x] = prev
        prev = now
    ## 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
    ## 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

    # print("공기청정기 작동 후 :")
    # for m in maps:
    #     print(m)

answer = 0

for y in range(r):
    for x in range(c):
        if maps[y][x] > 0:
            answer += maps[y][x]
print(answer)

 

 

확실히 문제의 요구사항을 주석으로 꼼꼼히 달면서 풀이하는게 좋은 것 같다.