📋 문제 요약
R×C 크기의 방에 미세먼지와 공기청정기가 있다. T초 동안 매 초마다 다음 두 가지 일이 순서대로 일어난다:
- 미세먼지 확산: 모든 칸에서 동시에 인접 4방향으로 확산
- 공기청정기 작동: 바람이 불어 미세먼지가 순환
T초 후 남아있는 미세먼지의 총량을 구하는 문제다.
🔍 문제 분석
1. 미세먼지 확산 규칙
각 칸 (r, c)에 있는 미세먼지 A가 확산될 때:
- 인접한 4방향(상하좌우)으로 각각
⌊A/5⌋만큼 확산 - 공기청정기가 있거나 격자 밖이면 그 방향으로는 확산 안 됨
- 원래 칸에 남는 양:
A - ⌊A/5⌋ × (확산된 방향 수)
핵심 포인트: 모든 칸에서 동시에 확산이 일어난다. 따라서 확산 결과를 새로운 배열에 저장해야 한다.
2. 공기청정기 바람 순환
공기청정기는 1열에 두 행을 차지하며 설치되어 있다:
- 위쪽 공기청정기: 반시계방향 순환
- 아래쪽 공기청정기: 시계방향 순환
바람이 불면 미세먼지가 한 칸씩 밀려나고, 공기청정기에서 나오는 바람은 깨끗하며(0), 공기청정기로 들어간 미세먼지는 정화된다(사라짐).
💡 솔루션 도출
Step 1: 전체 구조 설계
전형적인 시뮬레이션 문제다. T번의 루프를 돌면서 매번 확산과 순환을 수행하면 된다.
for _ in range(T):
확산()
순환()Step 2: 확산 구현 전략
"동시에 확산"을 구현하는 가장 확실한 방법은 새 배열을 만들어서 결과를 저장하는 것이다.
# 의사코드
new_grid = 빈 배열 생성
for 모든 칸 (r, c):
if 공기청정기:
new_grid[r][c] = -1
elif 미세먼지 있음:
확산량 = grid[r][c] // 5
for 인접 4방향:
if 유효한 칸 and 공기청정기 아님:
new_grid[인접칸] += 확산량
확산 횟수 += 1
new_grid[r][c] += grid[r][c] - 확산량 * 확산 횟수
grid = new_gridStep 3: 순환 구현 전략
순환은 "밀기"보다 "당기기"로 구현하는 것이 덜 헷갈린다.
예를 들어 위쪽 공기청정기(반시계방향)의 경우:
공기청정기 위치를 top이라 하면:
1. 왼쪽 열: 위로 당기기 (아래→위)
g[r][0] = g[r-1][0] (r: top-1 → 1)
2. 윗줄: 왼쪽으로 당기기 (오른쪽→왼쪽)
g[0][c] = g[0][c+1] (c: 0 → C-2)
3. 오른쪽 열: 아래로 당기기 (위→아래)
g[r][C-1] = g[r+1][C-1] (r: 0 → top-1)
4. 공기청정기 행: 오른쪽으로 당기기 (왼쪽→오른쪽)
g[top][c] = g[top][c-1] (c: C-1 → 2)
5. 공기청정기에서 나오는 바람은 깨끗
g[top][1] = 0순서가 중요하다! 값이 덮어씌워지기 전에 당겨와야 하므로, 공기청정기에서 멀어지는 방향부터 처리한다.
Step 4: 공기청정기 위치 찾기
입력에서 -1이 나오는 두 행을 찾으면 된다. 문제 조건상 두 -1은 연속된 행에 있다.
⚡ 최적화 포인트
1. 입력 최적화
한 번에 모든 입력을 읽어서 처리:
R,C,T,*d = map(int, open(0).read().split())
g = [[d[r*C+c] for c in range(C)] for r in range(R)]2. 조건 분기 최소화
확산 시 v=0인 경우를 elif v:로 빠르게 스킵:
if v == -1:
n[r][c] = -1
elif v: # v > 0인 경우만 처리
# 확산 로직3. 함수 호출 오버헤드 제거
함수로 분리하지 않고 메인 루프에 인라인으로 작성하면 약간의 성능 향상이 있다.
4. 결과 계산
전체 합계에서 공기청정기(-1 두 개)를 보정:
print(sum(sum(row) for row in g) + 2)✅ 최종 코드
def s():
R,C,T,*d=map(int,open(0).read().split())
g=[[d[r*C+c]for c in range(C)]for r in range(R)]
t=b=0
for r in range(R):
if g[r][0]==-1:
if t:
b=r
else:
t=r
for _ in range(T):
n=[[0]*C for _ in range(R)]
for r in range(R):
for c in range(C):
v=g[r][c]
if v==-1:
n[r][c]=-1
elif v:
a=v//5
k=0
for nr,nc in((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
if 0<=nr🔑 변수 설명
| 변수 | 의미 |
|---|---|
g |
현재 격자 상태 |
n |
확산 후 새 격자 |
t |
위쪽 공기청정기 행 (top) |
b |
아래쪽 공기청정기 행 (bottom) |
v |
현재 칸의 미세먼지 양 (value) |
a |
확산량 v//5 (amount) |
k |
확산된 방향 수 (count) |
⏱️ 시간복잡도
O(T × R × C)
- T: 최대 1,000
- R, C: 최대 50
- 총 연산: 약 250만 회 → 1초 내 충분
📝 실수하기 쉬운 포인트
- 확산의 동시성: 새 배열을 사용하지 않으면 이미 확산된 값이 다시 확산되는 오류 발생
- 순환 순서: 당기는 순서가 잘못되면 값이 덮어씌워져서 손실됨
- 공기청정기 출력: 순환 후
g[t][1] = 0과g[b][1] = 0을 빼먹으면 안 됨 - 결과 보정: 공기청정기 -1 두 개를 더해줘야 정확한 미세먼지 총량이 됨