[백준] 17144 미세먼지 안녕!

알고리즘

[백준] 17144 미세먼지 안녕! - 골드 4

swanzzz 2025. 6. 22. 00:18

[오늘의 문제]

https://www.acmicpc.net/problem/17144

[오늘의 학습 키워드]

구현
BFS

1. 문제설명

문제를 요약하자면

미세먼지가 가득한 방에 공기청정기를 가동시켜 미세먼지를 최대 T초간 제거 후 방에 남아있는 미세먼지의 총 양을 출력하는 문제입니다.

미세먼지는 1초동안 동시에 확산을 시작하는데

확산의 조건은 다음과 같습니다.

미세먼지는 인접한 4방향으로 확산한다.
인접한 방향에 공기청정기가 있거나, 벽이 있다면 확신이 일어나지 않는다.
확산되는 양은 현재 위치 (i, j) // 5 의 양 만큼 확산된다.
확산 후 현재 위치 (i, j) 에 남는 양은 확산된 미세먼지의 수 (i, j) // 5 x (확산된 미세먼지 수) 만큼 감소된다
1. 즉 i, j 는 (i, j) - (i, j) // 5 * 확산된 미세먼지 수 로 계산됩니다.
미세먼지가 확산될 때 이미 미세먼지가 존재한다면 합쳐진다.

미세먼지는 위와같은 조건으로 확산되어 움직입니다.

다음으로 공기청정기의 가동을 살펴보죠

공기청정기는 1초동안 다음과 같이 동작합니다.

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

이러한 방식으로 동작한다고 할 때 남아있는 미세먼지의 양을 구하는 문제 입니다.

[제한사항]

시간 제한 1초
메모리 제한 512MB
첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.
둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다.
공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다.
-1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

2. 접근방식

까다로워 보이는데 조건만 잘 살핀다면 쉽게 해결이 가능한 문제 입니다.

우선 가장 먼저 모든 동작은 T초간 발생합니다.

T초간 미세먼지가 확산되고, 공기청정기가 가동되죠

위 두 활동은 미세먼지 확산 후 공기청정기가 가동되는 순서이고 1초동안 동시에 발생합니다.

미세먼지는 1초동안 동시에 확산해야 하니 BFS를 떠올리 수 있죠 간단히 BFS로 미세먼지가 확산되면 다음에는 공기청정기가 가동되어야 하겠죠

공기청정기의 위치는 (i, 0) / (i+1, 0) 위치에 존재합니다. 여기서 i가 위쪽 공기청정기에 해당하고 i + 1이 아래쪽에 해당하겠죠

공기청정기에서 부는 바람은 위쪽은 우 -> 상 -> 좌 -> 하 순서로 불어야 하고

아래쪽에서 부는 바람은 우 -> 하 -> 좌 -> 상 순서로 불어야 합니다.

이는 한번의 정의에서 dir의 다른 접근으로 구해줄 수 있습니다.

우 -> 상 -> 좌 -> 하 순서로 dx, dy를 구성하고 dir을 1부터 접근할 때

위쪽 공기청정기는 1부터 증가하며 접근하면 그대로 우, 상, 좌, 하 순서로 접근이 가능하고

아래쪽 공기청정기는 dir을 1부터 거꾸로 접근하면 우, 하, 좌, 상 순서로 접근이 가능하겠죠

이렇게 공기청정기가 가동될 때 공기청정기에서 나오는 바람은 미세먼지가 없기 때문에 0으로 표시해주면 되겠죠

공기청정기에서 바람이 불어 한칸씩 이동할 때 현재위치의 값을 temp에 저장하고 temp에 저장된 값을 현재 위치에 내려 놓습니다.

이 과정을 반복하면 다음번 위치에는 현재 위치의 미세먼지 값이 temp에 저장되어 있기 때문에 한칸씩 밀어놓을 수 있습니다.

간단히 bubble sort를 활용해주면 될 것 같습니다.

공기청정기가 순환하다가 다시 공기청정기를 만나게 되면 마지막 위치의 미세먼지가 공기청정기로 돌아왔다는 의미가 되니 해당 미세먼지는 정화되고 공기청정기의 동작이 종료되어야 하겠죠

이렇게 미세먼지의 확산과 공기청정기의 동작이 종료되면 T초동안 계속 반복되어야 하니 다시 미세먼지의 위치를 찾아서 queue에 저장해 주어야 동시에 확산이 가능하겠죠

이런순서로 접근한다면 문제를 해결할 수 있을것 같습니다.

코드로 설명하죠

3. 코드

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

# 방향 중요 / 우 -> 상 -> 좌 -> 하 순서
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

# 먼지 확산
def BFS(queue):
    while queue:
        x, y, value = queue.popleft()

        count = 0   # 남은 먼지의 크기 계산용
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]

            # 벽이거나 공기청정기 위치는 X
            if 0 <= nx < N and 0 <= ny < M and room[nx][ny] != -1:
                    room[nx][ny] += value // 5
                    count += 1

        # 먼지 확산 후 남은 먼지의 양
        room[x][y] -= (value // 5) * count

# 공기청정기 가동 2방향
def action(air):
    # 위쪽 공청기 순환 시작
    x, y = air[0], 1    # 공기청정기 바로 오른쪽 위치부터 밀어내기
    dir = 0             # 방향 우 -> 상 -> 좌 -> 하
    temp = 0            # 해당 위치에 있던 값 저장할 임시변수
    while True:
        nx = x + dx[dir]
        ny = y + dy[dir]

        # 종료조건 -> 바람이 순환하다가 공기청정기에 다시 들어가면 종료
        if (x, y) == (air[0], 0):
            break

        # 벽에 부딪히면 방향 전환
        if not (0 <= nx < N and 0 <= ny < M):
            dir = (dir + 1) % 4
            continue

        # 해당 위치의 값 temp에 저장하고 tmep에 있던 값 해당 위치에 내려놓는 식으로 배열 순환
        room[x][y], temp = temp, room[x][y]
        x, y = nx, ny

    # 아래쪽 공청기 순환 시작
    x, y = air[1], 1
    dir = 0
    temp = 0
    while True:
        nx = x + dx[dir]
        ny = y + dy[dir]

        # 종료조건 -> 바람이 순환하다가 공기청정기에 다시 들어가면 종료
        if (x, y) == (air[1], 0):
            break

        # 벽에 부딪히면 방향 전환
        if not (0 <= nx < N and 0 <= ny < M):
            dir = (dir - 1) % 4
            continue

        # 해당 위치의 값 temp에 저장하고 tmep에 있던 값 해당 위치에 내려놓는 식으로 배열 순환
        room[x][y], temp = temp, room[x][y]
        x, y = nx, ny

# 입력
N, M, T = map(int, input().split())
room = [list(map(int, input().split())) for _ in range(N)]

air_purifier = []   # 공기청정기 위치
for _ in range(T):
    dust = deque()  # 먼지 위치

    for i in range(N):
        for j in range(M):

            # 먼지 위치 저장
            if room[i][j] > 0:
                dust.append((i, j, room[i][j]))

            # 공기청정기 위치 저장
            if room[i][j] == -1:
                air_purifier.append(i)

    # 먼지확산, 공기청정기 가동 순서
    BFS(dust)
    action(air_purifier)

answer = 0
for i in range(N):
    for j in range(M):
        if room[i][j] > 0:
            answer += room[i][j]
print(answer)

[코드설명]

# 입력
N, M, T = map(int, input().split())
room = [list(map(int, input().split())) for _ in range(N)]

air_purifier = []   # 공기청정기 위치
for _ in range(T):
    dust = deque()  # 먼지 위치

    for i in range(N):
        for j in range(M):

            # 먼지 위치 저장
            if room[i][j] > 0:
                dust.append((i, j, room[i][j]))

            # 공기청정기 위치 저장
            if room[i][j] == -1:
                air_purifier.append(i)

    # 먼지확산, 공기청정기 가동 순서
    BFS(dust)
    action(air_purifier)

저는 입력을 N, M 으로 받는걸 선호하여 이렇게 작성하였습니다.

T초 동안 미세먼지의 확산과, 공기청정기의 동작이 실시되어야 하며 미세먼지는 매초 동시에 확산되니 1초가 지난 순간 미세먼지들의 위치가 달라지겠죠

이를 계산해주려면 전체를 T초동안 반복할 때 매번 미세먼지의 위치를 찾아서 queue에 넣어주고 BFS를 실행해주면 됩니다.

BFS를 실행하고 공기청정기가 동작해야하니 두 동작을 구분해서 각각 BFS와 action 함수로 작성해 주었습니다.

# 방향 중요 / 우 -> 상 -> 좌 -> 하 순서
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

# 먼지 확산
def BFS(queue):
    while queue:
        x, y, value = queue.popleft()

        count = 0   # 남은 먼지의 크기 계산용
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]

            # 벽이거나 공기청정기 위치는 X
            if 0 <= nx < N and 0 <= ny < M and room[nx][ny] != -1:
                    room[nx][ny] += value // 5
                    count += 1

        # 먼지 확산 후 남은 먼지의 양
        room[x][y] -= (value // 5) * count

BFS 동작할 때는 방향이 중요하지 않지만 공기청정기의 동작에는 방향이 중요하기 때문에 dx dy를 방향에 맞춰 작성해 주었습니다.

BFS 동작으로 먼지가 확산될 때 확산되는 위치와 양, 현재 위치에 남게되는 미세먼지의 양을 계산해 주어야 합니다.

현재 위치에 남게되는 미세먼지의 양을 구하기 위해서 count 변수를 작성하고 미세먼지가 확산될 때 count를 증가시켜 줍니다.

확산이 종료되면 현재 위치의 미세먼지 양은 확산된 양 x count로 구해줄 수 있으니 이런방식으로 초기화 해줍니다.

# 공기청정기 가동 2방향
def action(air):
    # 위쪽 공청기 순환 시작
    x, y = air[0], 1    # 공기청정기 바로 오른쪽 위치부터 밀어내기
    dir = 0             # 방향 우 -> 상 -> 좌 -> 하
    temp = 0            # 해당 위치에 있던 값 저장할 임시변수
    while True:
        nx = x + dx[dir]
        ny = y + dy[dir]

        # 종료조건 -> 바람이 순환하다가 공기청정기에 다시 들어가면 종료
        if (x, y) == (air[0], 0):
            break

        # 벽에 부딪히면 방향 전환
        if not (0 <= nx < N and 0 <= ny < M):
            dir = (dir + 1) % 4
            continue

        # 해당 위치의 값 temp에 저장하고 tmep에 있던 값 해당 위치에 내려놓는 식으로 배열 순환
        room[x][y], temp = temp, room[x][y]
        x, y = nx, ny

    # 아래쪽 공청기 순환 시작
    x, y = air[1], 1
    dir = 0
    temp = 0
    while True:
        nx = x + dx[dir]
        ny = y + dy[dir]

        # 종료조건 -> 바람이 순환하다가 공기청정기에 다시 들어가면 종료
        if (x, y) == (air[1], 0):
            break

        # 벽에 부딪히면 방향 전환
        if not (0 <= nx < N and 0 <= ny < M):
            dir = (dir - 1) % 4
            continue

        # 해당 위치의 값 temp에 저장하고 tmep에 있던 값 해당 위치에 내려놓는 식으로 배열 순환
        room[x][y], temp = temp, room[x][y]
        x, y = nx, ny

공기청정기는 각각 위쪽과 아래쪽 2방향이 가동되어야 합니다.

가동의 원리는 비슷한데 바람의 순환 방향이 다르기 때문에 구분해서 작성해 주었습니다.

위쪽의 공기청정기의 위치는 air_purifier의 0번째 위치에 저장되어있고 아래쪽은 1번에 저장되어 있죠

이를 air로 받아올 때, air[0] 이 위쪽 공기청정기, air[1]이 아래쪽 공기청정기에 해당합니다.

순환하다 벽을 만나는 경우 방향전환이 발생해야 하니 dx, dy를 정해줄 dir을 작성해 주었습니다.

이제 종료조건에 맞춰 순환이 발생해야 하니 while문을 이용해 바람의 순환이 실시됩니다.

가장 먼저 종료조건은 바람의 위치가 다시 공기청정기로 돌아오는 순간 종료됩니다.

공기청정기의 위치는 각각 i, 0 / i+1, 0 이니 해당 위치로 x, y가 들어오는 순간 종료해 주어야겠죠

바람이 순환하다 벽에 부딪히는 경우 방향전환이 발생하는데 이는 위쪽은 dir + 1, 아래쪽은 dir-1로 구현해 주었습니다.

바람이 순환하며 미세먼지가 1칸씩 밀려야 하기 때문에 현재위치의 공기를 저장할 temp를 선언하고 bubble sort를 활용해 1칸씩 밀어줍니다.

동시에 x, y의 위치는 계속해서 바뀌어야 하기 때문에 x, y 를 nx, ny로 바꿔주게 되죠

answer = 0
for i in range(N):
    for j in range(M):
        if room[i][j] > 0:
            answer += room[i][j]
print(answer)

모든 동작이 완료 되었을 때 결과를 출력해 주었습니다.

4. 결과

[회고]

이번 문제는 그렇게 어려운 문제는 아니었습니다.

한가지 했던 실수는 T초동안 미세먼지가 확산될 때 확산 후 다시 미세먼지의 위치를 구해 dust에 저장하지 않았던 것인데

예제 1번과 2번의 경우 T가 1초 2초인데 2초까지 미세먼지가 확산되더라도 제거되는 미세먼지가 없고 미세먼지의 양이 바뀌지 않아서 통과가 되었는데 예제 3번부터 틀려서 어? 했던 실수였습니다.

모든 조건에 맞춰 다 구현하니 1번과 2번은 제대로 출력이 되었는데 3번부터 다르게 출력되어 어디가 문제지 고민을 했습니다.

조건을 다시 살펴보고 노트에 작성한 코드를 다시 살펴보다가 BFS로 미세먼지 확장 후 다시 미세먼지의 위치를 구하지 않았던 것을 깨닫고 수정하여 통과한 문제 였습니다.

가끔 문제를 풀다보면 너무 당연한 조건이라 생각하여 구현했다 착각하고 하지않아 종종 틀리는 경우가 있습니다.

많은 문제를 풀어도 이런식의 실수가 나오는 것을 보면 아직 더 많은 문제를 풀고 해결해야 할 것 같습니다.

'알고리즘' 카테고리의 다른 글

[백준]15684 사다리 조작 - 골드 3 (0)	2025.06.23
[백준] 20055 컨베이어 벨트 위의 로봇 - 골드 5 (0)	2025.06.22
[백준]14890 경사로 - 골드 (0)	2025.06.21
[백준]14500 테트로미노 - 골드 4 (0)	2025.06.19
[백준] 3190 뱀 - 골드 4 (2)	2025.06.17

현재글[백준] 17144 미세먼지 안녕! - 골드 4

swanzzz 님의 블로그

프론트엔드 개발자로 취준중인 swan입니다.

dfs, 너비 우선 탐색, 골드 5, 프로그래머스, SSAFY, DP, 골드4, 백준, 실버 2, HTML5, 골드 4, 골드 3, BFS, 그래프 탐색, 구현, 그래프 이론, 파이썬, 골드5, React, CSS3,

Today :
Yesterday :

swanzzz 님의 블로그