개인적으로 구현 많은 문제를 풀면 뚝딱뚝딱 만들어내는 로봇이 된 것만 같아 왠지 뿌듯하다.
근데 그것도 적당히 해야지, 구현이 선을 넘게 많은 문제들이 간혹 있다.
그 중에서 solved.ac Class 4에 포함되어 있는 미세먼지 안녕! 이라는 문제를 풀이해보겠다.
(언젠가부터 미세먼지 심한 날씨가 사라진 것 같다. 못느낀건가..?)

BOJ 17144 - 미세먼지 안녕! 링크
(2022.08.30 기준 G4)
(치팅하면 미세먼지 다 거기로 감!)

문제

T초가 지났을 때, 방에 남아 있는 미세먼지 상태를 출력

알고리즘

특별한 알고리즘은 없다. 시간에 따른 미세먼지의 확산 및 공기청정기의 바람에 의한 미세먼지의 변화하는 것을 시뮬레이션 돌린다고 생각하면 된다.
진짜 별거 없다. 그냥 구현이 많다.

풀이

1초 동안 아래 적힌 일이 순서대로 일어난다.

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

• (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
• 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
• 확산되는 양은 Ar,c/5이고 소수점은 버린다.
• (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.

2. 공기청정기가 작동한다.

• 공기청정기에서는 바람이 나온다.
• 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
• 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
• 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

우리가 구현해야 할 것들이다.
그냥 차례대로 뚝딱뚝딱 구현해나가면 되는데.. 문제는 미세먼지 확산 시에 미세먼지 상태를 담은 행렬 하나만 사용하면, 현재와 미래의 상태가 겹쳐버린다.

문제 지문에 예시에 있는 상태인데 만약 행렬 하나만 사용한다면 위 그림처럼 확산이 될 것이다.
직관적으로 한눈에 잘못됨을 느낄 수가 있을 것이다. 물론, 확산 전 상태를 다른 곳에 저장하여 해도 되겠지만 그러면 T번 행렬을 복사해야 하기 때문에 시간 초과가 난다.

그래서 내가 생각한 해결방법은 행렬을 두 개를 만들어서 t초가 홀수이냐 짝수이냐에 따라 쓰고 받는 행렬을 바꿔주는 것이다.

물론 확산 전 행렬은 확산시켜서 상태를 넘겨줄 때마다 확산시킨 칸은 0으로 초기화해준다. 그래야 확산 후 상태를 받는 행렬이 됐을 때, 수월하게 온전히 받을 수 있기 때문이다.

그 다음은, 공기청정기의 바람.
이것은 별거 없다. 값이 바뀐다던지 하는게 아니라 그냥 한칸씩 옮겨주고 마지막에 공기청정기로 들어가는 미세먼지는 없애주면 된다.
그냥 끝에 부딪힐 때마다 바람의 방향을 잘 바꿔주는 것만 조심해주면 된다.
위쪽 바람은 끝에 부딪힐 때마다 왼쪽으로 꺾이고, 반대로 아래쪽 바람은 끝에 부딪힐 때마다 오른쪽으로 꺾이는 것. 말고는 별거 없다.

위에서 설명한 것 말고는 그냥 생각나는 대로 구현해주면 된다. 참 쉽죠?

코드

import sys; input = sys.stdin.readline

# 흐른 시간이 홀수냐 짝수냐에 따라 주고 받는 행렬을 다르게 함

# 미세먼지 확산
def spread(i):
    if i % 2: # 홀수일 때
        for r in range(R):
            for c in range(C):
                if m_even[r][c] > 0: # 칸에 미세먼지가 있으면
                    o = m_even[r][c]
                    s = o // 5 # 확산되는 양은 나누기 5의 몫
                    for rr, cc in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:
                        # 인접한 4방향을 검사
                        # R과 C 범위 안이고, 공기청정기가 있는 곳이 아니어야 한다.
                        if 0 <= rr < R and 0 <= cc < C and not ((purifier_up_r == rr or purifier_down_r == rr) and purifier_c == cc):
                            m_odd[rr][cc] += s # 받는 행렬의 칸에 확산 양 추가
                            o -= s # 남아 있는 미세먼지는 감소
                    m_odd[r][c] += o # 남아 있는 미세먼지를 받는 행렬의 칸에 추가
                m_even[r][c] = 0 # 마지막으로 주는 행렬의 칸은 0으로 초기화
    else: # 짝수일 때. 밑은 홀수일 때와 동일
        for r in range(R):
            for c in range(C):
                if m_odd[r][c] > 0:
                    o = m_odd[r][c]
                    s = o // 5
                    for rr, cc in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:
                        if 0 <= rr < R and 0 <= cc < C and not ((purifier_up_r == rr or purifier_down_r == rr) and purifier_c == cc):
                            m_even[rr][cc] += s
                            o -= s
                    m_even[r][c] += o
                m_odd[r][c] = 0

# 공기청정기 위쪽 바람
def wind_up(r, c, dr, dc, dust, i):

    # 현재 위치가 공기청정기이면 멈춤
    if purifier_up_r == r and purifier_c == c:
        return

    if r == 0: # 현재 위치가 맨 위일 때
        if c == 0: # 그리고 맨 왼쪽일 때
            # 바람 방향은 밑으로
            dr = 1
            dc = 0
        elif c == C - 1: # 아니면 맨 오른쪽일 때
            # 바람 방향은 왼쪽으로
            dr = 0
            dc = -1
    elif c == C - 1 and dr == 0 and dc == 1: # 현재 위치가 맨 오른쪽이고 바람 방향이 오른쪽일 때
        # 바람 방향은 위로
        dr = -1
        dc = 0
    
    # 전 위치에 있던 먼지(dust)를 현재 위치에 넣고
    # 현재 위치에 있던 먼지를 다음 위치에 넣어야 하므로 dust에 저장하여 다음 함수로 넘겨준다.
    if i % 2: # 홀수일 때
        m_odd[r][c], dust = dust, m_odd[r][c]
    else: # 짝수일 때
        m_even[r][c], dust = dust, m_even[r][c]
    
    # 이를 끝날 때까지 다음 위치로 재귀
    wind_up(r + dr, c + dc, dr, dc, dust, i)

# 공기청정기 아래쪽 바람. 위쪽 바람 함수와 구조가 같다. 설명은 생략
def wind_down(r, c, dr, dc, dust, i):
    if purifier_down_r == r and purifier_c == c:
        return
    if r == R - 1:
        if c == 0:
            dr = -1
            dc = 0
        elif c == C - 1:
            dr = 0
            dc = -1
    elif c == C - 1 and dc == 1:
        dr = 1
        dc = 0
    if i % 2:
        m_odd[r][c], dust = dust, m_odd[r][c]
    else:
        m_even[r][c], dust = dust, m_even[r][c]
    wind_down(r + dr, c + dc, dr, dc, dust, i)

R, C, T = map(int, input().split())
m_even = [list(map(int, input().split())) for _ in range(R)] # 처음에는 0초이므로 짝수 행렬에 미세먼지 상태를 담아준다.
m_odd = [[0] * C for _ in range(R)]
flag = False
for r in range(R):
    if flag: break
    for c in range(C):
        if m_even[r][c] == -1: # 공기청정기를 찾아서 위치를 따로 저장
            purifier_c = c
            purifier_up_r = r
            purifier_down_r = r + 1
            flag = True
            break

# T초가 지날 때까지 확산시키고 공기청정기 위쪽과 아래쪽 바람을 불어주자
for t in range(1, T + 1):
    spread(t)
    wind_up(purifier_up_r, purifier_c + 1, 0, 1, 0, t)
    wind_down(purifier_down_r, purifier_c + 1, 0, 1, 0, t)

# 남아 있는 미세먼지의 합을 출력. T초가 홀수이냐 짝수이냐에 따라 다르게 하자.
if T % 2:
    print(sum(sum(m) for m in m_odd))
else:
    print(sum(sum(m) for m in m_even))

여담

이 문제는 트릭이 없는 정직한 문제지만 구현이 꽤 많아 중간에 한번 틀리면 디버깅의 늪에 빠지는 그런 문제인 듯 하다.
골드 이상의 문제를 많이 접하지 않은 사람이 이런 문제를 처음 마주하면 꽤나 당황스러울 것이다. (나도 그랬었다)
하지만 차근차근 디버깅하면서 풀어내면, 특정한 알고리즘 실력이 아닌 코딩 그 자체의 실력이 조금 더 탄탄해질 것이라고 믿어 의심치 않는다. 그러니 모두들 파이팅!