백준 17144번 - 미세먼지 안녕!
미세먼지 안녕! 문제 바로 가기
풀이 날짜: 2026-04-07
baekjoon 알고리즘 문제 풀이
풀이 코드
from collections import deque
n,m,t = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
dx = [0,0,-1,1]
dy = [-1,1,0,0]
# 공기청정기 위치
robot = []
for i in range(n):
for j in range(m):
if graph[i][j] == -1:
robot.append((i,j))
top = robot[0][0]
bottom = robot[1][0]
#미세먼지 확산
def spread():
temp = [[0]*m for _ in range(n)]
for x in range(n):
for y in range(m):
if graph[x][y] > 0:
dust = graph[x][y] // 5
count = 0
for i in range(4):
nx = dx[i] + x
ny = dy[i] + y
if 0<=nx<n and 0<=ny<m and graph[nx][ny] != -1:
temp[nx][ny] += dust
count += 1
temp[x][y] += graph[x][y] - dust * count
temp[top][0] = -1
temp[bottom][0] = -1
return temp
#공기청정기 작동
def air():
for i in range(top-1,0,-1):
graph[i][0] = graph[i-1][0]
for i in range(m-1):
graph[0][i] = graph[0][i+1]
for i in range(top):
graph[i][m-1] = graph[i+1][m-1]
for i in range(m-1,1,-1):
graph[top][i] = graph[top][i-1]
graph[top][1] = 0
for i in range(bottom+1,n-1):
graph[i][0] = graph[i+1][0]
for i in range(m-1):
graph[n-1][i] = graph[n-1][i+1]
for i in range(n-1, bottom, -1):
graph[i][m-1] = graph[i-1][m-1]
for i in range(m-1,1,-1):
graph[bottom][i] = graph[bottom][i-1]
graph[bottom][1] = 0
graph[top][0] = -1
graph[bottom][0] = -1
for _ in range(t):
graph = spread()
air()
answer = 0
for i in range(n):
for j in range(m):
if graph[i][j] > 0:
answer += graph[i][j]
print(answer)
접근 방법
단순한 BFS나 DFS처럼 한 가지 알고리즘만 적용해서 해결하는 문제가 아니라, 문제에서 요구하는 상황을 그대로 코드로 옮겨야 하는 구현 + 시뮬레이션 문제였다. 처음 문제를 봤을 때는 “미세먼지가 확산되고, 공기청정기가 작동한다”는 문장이 직관적으로 이해되는 것 같았지만, 실제로 이를 코드로 구현하려고 하니 생각보다 훨씬 복잡했다. 특히 한 턴 안에서 미세먼지 확산과 공기청정기 작동이 순서대로 일어나기 때문에, 이 두 과정을 정확히 분리해서 구현해야 한다는 점이 어려웠다.
처음에는 단순히 현재 배열에서 미세먼지를 바로 퍼뜨리면 되겠다고 생각했지만, 그렇게 하면 이미 확산된 값이 또 다음 칸 확산 계산에 영향을 주게 된다. 이 문제는 결국 “현재 상태를 기준으로 동시에 확산되는 것처럼 계산해야 한다”는 점을 이해하는 것이 핵심이었다. 즉, 단순히 반복문만 잘 돌린다고 끝나는 문제가 아니라, 상태를 보존하면서 다음 상태를 만들어야 하는 전형적인 시뮬레이션 문제였다.
핵심 아이디어
이 문제는 전체적으로 보면 매 초마다 다음 두 단계가 반복된다.
첫 번째는 미세먼지 확산이다. 각 칸에 있는 미세먼지는 주변 네 방향으로 확산될 수 있고, 확산되는 양은 현재 먼지 양 // 5이다. 다만 공기청정기가 있는 칸으로는 확산되지 않고, 격자 범위를 벗어나는 방향 역시 무시해야 한다. 또한 여러 방향으로 동시에 퍼져야 하므로, 확산 결과는 원래 배열에 바로 반영하면 안 된다.
두 번째는 공기청정기 작동이다. 공기청정기는 두 칸을 차지하고 있으며, 위쪽 공기청정기는 반시계 방향으로, 아래쪽 공기청정기는 시계 방향으로 공기를 순환시킨다. 이 과정에서 미세먼지는 공기의 흐름을 따라 한 칸씩 이동하며, 공기청정기 바로 오른쪽 칸으로는 깨끗한 공기가 들어오기 때문에 그 칸은 0이 된다.
즉 이 문제는 한 번의 연산이 끝나는 구조가 아니라, “확산 → 공기청정기 작동”을 t초 동안 반복하는 방식으로 해결해야 한다.
내가 이 문제에서 가장 어렵게 느낀 부분
이 문제를 풀면서 가장 어려웠던 부분은 공기청정기 순환 방향 구현보다도, 사실 그 전에 좌표와 배열 조작 개념을 정확하게 이해하는 것이었다. 예를 들어 robot.append((i, j))처럼 공기청정기 위치를 튜플로 저장한 뒤, top = robot[0][0], bottom = robot[1][0]처럼 행 번호만 따로 빼는 부분조차 처음에는 직관적으로 잘 와닿지 않았다. (행, 열)이라는 좌표 개념은 알고 있었지만, 리스트 안에 좌표가 들어 있고, 그 좌표에서 다시 행 번호만 꺼내서 사용하는 구조가 익숙하지 않았기 때문이다.
또 하나 어려웠던 점은, 공기청정기 바로 오른쪽 칸을 왜 graph[top][1]로 표현하는지 이해하는 것이었다. top이라는 변수가 단순히 숫자 하나라는 점, 그 숫자가 “위쪽 공기청정기의 행 번호”라는 점, 그리고 공기청정기는 항상 첫 번째 열에 있기 때문에 오른쪽 칸은 열 번호가 1이라는 점이 머릿속에서 한 번에 연결되지 않았다. 결국 이 문제는 코드를 외우는 게 아니라, 배열의 좌표가 실제 공간에서 어떤 위치를 의미하는지 시각적으로 이해해야 한다는 걸 느꼈다.
미세먼지 확산을 구현할 때 중요한 점
핵심은 기존 배열 graph를 바로 수정하면 안 된다는 점이다. 이유는 현재 칸의 먼지가 확산되는 도중에, 이미 확산된 값이 다른 칸의 계산에 섞이면 안 되기 때문이다. 문제에서는 모든 미세먼지가 동시에 퍼지는 것처럼 처리해야 하므로, 새로운 배열 temp를 만들어 확산 결과를 따로 저장해야 한다.
각 칸에 대해 graph[x][y] > 0이면 미세먼지가 있다는 뜻이므로 확산을 시도한다. 이때 확산되는 양은 graph[x][y] // 5이며, 네 방향 중 실제로 확산 가능한 방향 수를 세기 위해 count 변수를 사용한다. 확산 가능한 방향은 격자 범위 안이면서 공기청정기 칸이 아닌 경우이다. 가능한 방향으로는 temp[nx][ny] += dust를 해주고, 몇 방향으로 퍼졌는지를 count에 누적한다. 마지막에는 원래 칸에 남아 있어야 할 먼지 양, 즉 원래 먼지 - (퍼져나간 양)을 temp[x][y]에 더해준다.
이 과정에서 내가 새롭게 이해한 점은, 시뮬레이션 문제에서는 현재 상태와 다음 상태를 섞지 않는 것이 매우 중요하다는 것이다. temp 배열은 단순한 임시 저장소가 아니라, 동시성을 코드로 구현하기 위한 장치라고 볼 수 있다.
공기청정기 위치를 다시 -1로 넣어야 하는 이유
확산이 끝난 후 temp[top][0] = -1, temp[bottom][0] = -1를 다시 해줘야 한다는 점도 처음에는 굉장히 헷갈렸다. 처음에는 “공기청정기는 원래 graph에 이미 있었는데 왜 또 넣지?”라는 생각이 들었다. 하지만 곰곰이 보면 temp는 매 턴마다 새로 만든 배열이기 때문에, 처음에는 모든 칸이 0으로 초기화된다. 즉 원래 graph에서 공기청정기였던 자리도 temp에서는 자동으로 0이 되어버린다.
따라서 확산 계산이 끝난 뒤에는, 공기청정기가 있는 위치를 다시 -1로 복구해줘야 한다. 이 작업은 단순히 값 하나를 넣는 것이 아니라, 다음 단계인 공기청정기 작동을 위해 반드시 필요한 복원 작업이다. 만약 이 과정을 하지 않으면, 이후 순환 과정에서 공기청정기 위치를 기준으로 작동해야 하는 로직이 무너지게 된다.
이 부분을 통해 구현 문제에서는 단순히 계산만 맞추는 것이 아니라, 문제에서 특별한 의미를 가지는 칸이나 상태를 끝까지 유지하는 것도 중요하다는 것을 배웠다.
공기청정기 작동 구현이 어려웠던 이유
공기청정기 작동 부분은 이 문제의 핵심이자 가장 구현 난도가 높은 구간이었다. 위쪽 공기청정기는 반시계 방향, 아래쪽 공기청정기는 시계 방향으로 공기를 순환시키는데, 이 흐름을 코드로 바꾸는 것이 생각보다 까다로웠다. 특히 “어느 칸이 어느 칸의 값을 가져와야 하는지”를 정확하게 정리하지 않으면 인덱스가 금방 꼬인다.
예를 들어 위쪽 공기청정기에서는 왼쪽 열이 아래에서 위로 밀리고, 맨 윗줄은 오른쪽에서 왼쪽으로 밀리며, 오른쪽 열은 위에서 아래로 내려오고, 공기청정기 행은 왼쪽에서 오른쪽으로 이동한다. 처음에는 이 방향이 계속 헷갈렸고, graph[0][i] = graph[0][i+1]처럼 왜 오른쪽 값을 현재 칸으로 가져오는지도 잘 이해되지 않았다. 하지만 공기가 왼쪽으로 이동한다는 것은 결국 현재 칸이 오른쪽 칸의 값을 받는 것이라고 생각하니 훨씬 이해가 쉬워졌다.
즉 이 문제는 “값을 밀어낸다”기보다, 현재 칸이 어느 방향의 값을 받아와야 하는가로 생각해야 한다. 이 관점으로 바꾸고 나니 반복문의 방향과 대입문 구조가 조금씩 보이기 시작했다.
전체 풀이 흐름 정리
먼저 입력을 받고, 공기청정기의 두 위치를 찾아 위쪽과 아래쪽 공기청정기의 행 번호를 저장한다. 이후 t초 동안 반복문을 돌면서, 먼저 spread()를 호출해 미세먼지 확산 결과를 새 배열로 만든 뒤 graph를 갱신한다. 그 다음 air()를 호출해 공기청정기를 작동시키고, 위쪽과 아래쪽 공기 순환을 각각 구현한다. 이 과정을 모두 마치면 최종 배열에 남아 있는 먼지 양을 합산하여 정답을 출력한다.
즉 핵심은 단순히 한 번의 계산이 아니라, 매 초마다 상태를 갱신하는 시뮬레이션을 정확하게 반복하는 것이다.
이 문제를 통해 배운 점
이번 문제를 풀면서 가장 크게 느낀 점은, 구현 문제에서는 코드 문법 자체보다도 상황을 배열 위에서 어떻게 표현할지가 훨씬 중요하다는 것이다. BFS나 DFS 문제는 어느 정도 익숙해지면 패턴이 보이지만, 시뮬레이션 문제는 문제에서 주어진 상황을 그대로 코드로 번역해야 하기 때문에 훨씬 더 꼼꼼한 사고가 필요하다.
특히 이번 문제를 통해 배운 것은 세 가지다. 첫째, 동시에 일어나는 변화를 구현할 때는 반드시 별도의 배열을 두어야 한다는 점이다. 둘째, 공기청정기처럼 특별한 의미를 갖는 위치는 계산 후에도 상태를 유지해야 한다는 점이다. 셋째, 순환이나 이동 문제에서는 “값이 어느 방향으로 움직이는가”보다 “현재 칸이 어느 칸의 값을 받아오는가”로 생각해야 구현이 훨씬 쉬워진다는 점이다.
처음에는 막막하고 어렵게 느껴졌지만, 한 줄 한 줄 뜯어보면서 결국 이 문제도 “좌표”와 “방향”을 정확히 다루는 문제라는 걸 이해하게 되었다. 앞으로 비슷한 시뮬레이션 문제가 나와도, 무작정 코드를 외우기보다 먼저 문제의 흐름을 그림으로 그려보고, 상태 변화 순서를 정리한 뒤 구현하는 습관을 가져야겠다고 느꼈다.
회고
이번 문제는 풀고 나서도 “완전히 내 것이 되었다”는 느낌보다는, 여러 번 다시 읽고 손으로 직접 흐름을 따라가야 비로소 이해가 되는 문제였다. 특히 공기청정기 순환 로직은 처음에는 거의 외우다시피 보였지만, 질문을 반복하면서 왜 그런 대입이 필요한지 조금씩 이해하게 되었다. 단순히 정답 코드를 얻는 것보다, 왜 그런 코드가 나오는지 이해하려고 끝까지 붙잡고 있었던 과정 자체가 더 의미 있었다고 생각한다.
앞으로도 구현 문제가 나오면 처음부터 완벽하게 이해하려고 하기보다는, 작은 좌표 예시를 그려보면서 각 줄이 실제로 어떤 변화를 만드는지 추적하는 방식으로 접근해야겠다. 이번 문제는 어렵고 오래 걸렸지만, 그만큼 배열과 시뮬레이션 감각을 키우는 데 큰 도움이 된 문제였다.