17144 - 미세먼지 안녕!

info

• 문제 보기: 17144 - 미세먼지 안녕!
• 소요 시간: 💥1시간 초과
• 풀이 언어: python
• 체감 난이도: 3️⃣~4️⃣ (3.8)
• 리뷰 횟수: ✅

풀이 키워드

스포주의

구현

풀이 코드

info

• 메모리: 35100 KB
• 시간: 4080 ms

import sys
from collections import defaultdict
input = sys.stdin.readline

r, c, t = 0, 0, 0
tdx, bdx = (-1, -1), (-1, -1) # 공기청정기 위/아래 좌표
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0] # R B L T
room = []
pcnt = 0 # purified dust count

def diffuse():
    dvMap = defaultdict(int) # diffuse value map
    
    for y in range(r):
        for x in range(c):
            if room[y][x] > 0:
                diffuseCnt = 0
                #y, x = dpos
                amount = room[y][x] // 5
                for i in range(4):
                    ny = y + dy[i]
                    nx = x + dx[i]
                    if 0 <= ny < r and 0 <= nx < c and ~room[ny][nx]:
                        dvMap[(ny, nx)] += amount
                        diffuseCnt += 1
                        
                room[y][x] = room[y][x] - amount * diffuseCnt
    
    # 확산은 동시에 일어나므로 확산지에 대한 모든 변화값을 합한 후 마지막에 합산
    for (y, x), v in dvMap.items():
        room[y][x] += v


def calc(y, x, d, ymn, ymx, isTop):
    ny = y + dy[d]
    nx = x + dx[d]
    
    # bound check
    if (not ymn <= ny < ymx) or (not 0 <= nx < c):
        d = (d-1 if isTop else d+1) % 4
        ny = y + dy[d]
        nx = x + dx[d]
    
    return (ny, nx, d)

def purify():
    global pcnt
    
    # top
    y, x = tdx
    ymn, ymx = 0, y+1
    d = 0 # direction index
    cur = 0
    
    while True:
        ny, nx, d = calc(y, x, d, ymn, ymx, True)
        nxt = room[ny][nx]
        if nxt == -1:
            pcnt += cur
            break
        else:
            room[ny][nx] = cur
        cur = nxt
        y, x = ny, nx
        
    # bottom
    y, x = bdx
    ymn, ymx = y, r
    d = 0 # direction index
    cur = 0
    
    while True:
        ny, nx, d = calc(y, x, d, ymn, ymx, False)
        nxt = room[ny][nx]
        if nxt == -1:
            pcnt += cur
            break
        else:
            room[ny][nx] = cur
        cur = nxt
        y, x = ny, nx
    

def solution():
    global r, c, tdx, bdx, room
    
    r, c, t = map(int, input().split())
    room = [[-2 for _ in range(c)] for _ in range(r)]
    
    isTop = True
    for i in range(r):
        data = list(map(int, input().split()))
        for j, v in enumerate(data):
            room[i][j] = v
            if v == -1: # 공기청정기면
                if isTop:
                    tdx = (i, j)
                    isTop = False
                else:
                    bdx = (i, j)
    
    # simulate
    total = sum(map(sum, room)) + 2 # 공기청정기 값 제외
    for _ in range(t):
        diffuse()
        purify()
    
    print(total - pcnt)
    

if __name__ == '__main__':
    solution()

풀이 해설

문제 그대로 구현하면 된다. 다만 주의할 점이 2가지 있는데

caution

1. 확산은 동시에 이루어진다.
   • 이를 서로 독립이라고 표현한다.
   • A 먼지의 확산이 B 먼지의 확산에 영향을 주면 안된다.
2. 확산시킬 먼지 스캔하는거 최적화한답시고 리스트에 좌표 넣어두면 안됨.
   • 공기청정기때문에 좌표가..... 이동하자너......

1번은 2차원 리스트 dvMap을 생성해서 합산할 값만 따로 모았다.

2번은 생각 못하고 좌표 저장해놨다가 정해랑 조금씩 값이 달라서 반례 고치는데 30분 걸림.

중간과정 출력해서 AC 코드 출력이랑 서로 diff 했는데 확산 결과가 다르길래 그제서야 로직 에러를 인지했다ㅜ

공기 순환 방향 전환시키기

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0] # R B L T

delta 리스트를 정방향 순회하면 시계방향, 역방향 순회하면 반시계방향이 되도록 작성했다.

# bound check
if (not ymn <= ny < ymx) or (not 0 <= nx < c):
    d = (d-1 if isTop else d+1) % 4

그리고 파이썬 모듈러 연산이 $-A\,\%\,B$ 를 수행할 경우 (단, $0 < A \le B$)

$(-A+B)\,\%\,B$ 로 치환하여 연산하는 특성을 이용해서 d가 음수가 될 경우를 처리함.

확산시킬 먼지 스캔하기

위에도 언급했듯 먼지 좌표 저장해두는건 공기청정기가 무결성을 깨뜨리기 때문에

대충 $O(N^2)$으로 스캔해서 처리했다.

for y in range(r):
    for x in range(c):
        if room[y][x] > 0:
            ...

메모

• 빡구현답게 짜증나지만 게리맨더링 2 보다는 나음.
• 빡구현은 거의 다 반례 유도형이라 걍 마지막에 풀어야 할 듯.