← Back to Blog

[백준 17144번 | C++] 미세먼지 안녕!

computer-science > problem-solving

2026-03-103 min read

#development #cs #cpp #problem-solving #graph

출처: 미세먼지 안녕!

시간 제한메모리 제한
1 초512 MB

문제

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

im1

공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

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

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

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

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

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

다음은 확산의 예시이다.

im2

왼쪽과 위쪽에 칸이 없기 때문에, 두 방향으로만 확산이 일어났다.

im3

인접한 네 방향으로 모두 확산이 일어난다.

im4

공기청정기가 있는 칸으로는 확산이 일어나지 않는다.

공기청정기의 바람은 다음과 같은 방향으로 순환한다.

im5

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

입력

첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.

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

출력

첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

풀이

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

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

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

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

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

문제 핵심 부분에 강조를 했다.

  1. 일이 순서대로 일어난다.
  2. 모든 칸에서 동시에 일어난다.

이 두 조건을 유념하면서 문제 풀이를 진행하면 된다.

일이 순서대로 일어난다고 하니, 미세먼지 확산을 먼저 해결해보자.
딱히 어려운 알고리듬은 없고, 문제에 작성된 그대로 구현하면 된다.

여기서 '모든 칸에서 동시에 일어난다.'를 조심해야 된다.
필자는 때문에 임시 그래프로 분리해 계산했다.

그래프 순회하면서 먼지를 퍼뜨린다. 이때 cnt로 퍼진 횟수를 저장해서, 나중에 값을 보정하는 식으로 구현했다.

void spread_graph(int graph[][51], int r, int c) {
    int temp_graph[51][51] = {0};
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    for (int x = 0; x < r; ++x) {
        for (int y = 0; y < c; ++y) {
            if (graph[x][y] == -1) {
                temp_graph[x][y] = -1;
                continue;
            }

            if (graph[x][y] > 0) {
                int spread = graph[x][y] / 5;
                int cnt = 0;

                for (int i = 0; i < 4; ++i) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];

                    if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
                    if (graph[nx][ny] == -1) continue;

                    temp_graph[nx][ny] += spread;
                    cnt++;
                }

                temp_graph[x][y] += graph[x][y] - spread * cnt;
            }
        }
    }

    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            graph[i][j] = temp_graph[i][j];
        }
    }
}

다음으로 구현해야 될 알고리듬은 공기청정기인데
이건 노가다하면 된다.


void air_purifier(int up, int down, int graph[][51], int r, int c) {
    // upper
    for (int i = up - 1; i > 0; --i) {
        graph[i][0] = graph[i - 1][0];
    }
    for (int j = 0; j < c - 1; ++j) {
        graph[0][j] = graph[0][j + 1];
    }
    for (int i = 0; i < up; ++i) {
        graph[i][c - 1] = graph[i + 1][c - 1];
    }
    for (int j = c - 1; j > 1; --j) {
        graph[up][j] = graph[up][j - 1];
    }
    graph[up][1] = 0;

    // lower
    for (int i = down + 1; i < r - 1; ++i) {
        graph[i][0] = graph[i + 1][0];
    }
    for (int j = 0; j < c - 1; ++j) {
        graph[r - 1][j] = graph[r - 1][j + 1];
    }
    for (int i = r - 1; i > down; --i) {
        graph[i][c - 1] = graph[i - 1][c - 1];
    }
    for (int j = c - 1; j > 1; --j) {
        graph[down][j] = graph[down][j - 1];
    }
    graph[down][1] = 0;

    graph[up][0] = -1;
    graph[down][0] = -1;
}

이제 이를 입력값 받고 순서대로 작동되게 하면 문제 해결이다.

전체코드

// 17144
#include <iostream>
using namespace std;

int graph[51][51];

void print_graph(int graph[][51], int r, int c) {
    cout << "===============" << '\n';
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            cout << graph[i][j] << ' ';
        }
        cout << '\n';
    }
}

void spread_graph(int graph[][51], int r, int c) {
    int temp_graph[51][51] = {0};
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    for (int x = 0; x < r; ++x) {
        for (int y = 0; y < c; ++y) {
            if (graph[x][y] == -1) {
                temp_graph[x][y] = -1;
                continue;
            }

            if (graph[x][y] > 0) {
                int spread = graph[x][y] / 5;
                int cnt = 0;

                for (int i = 0; i < 4; ++i) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];

                    if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
                    if (graph[nx][ny] == -1) continue;

                    temp_graph[nx][ny] += spread;
                    cnt++;
                }

                temp_graph[x][y] += graph[x][y] - spread * cnt;
            }
        }
    }

    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            graph[i][j] = temp_graph[i][j];
        }
    }
}

void air_purifier(int up, int down, int graph[][51], int r, int c) {
    // upper
    for (int i = up - 1; i > 0; --i) {
        graph[i][0] = graph[i - 1][0];
    }
    for (int j = 0; j < c - 1; ++j) {
        graph[0][j] = graph[0][j + 1];
    }
    for (int i = 0; i < up; ++i) {
        graph[i][c - 1] = graph[i + 1][c - 1];
    }
    for (int j = c - 1; j > 1; --j) {
        graph[up][j] = graph[up][j - 1];
    }
    graph[up][1] = 0;

    // lower
    for (int i = down + 1; i < r - 1; ++i) {
        graph[i][0] = graph[i + 1][0];
    }
    for (int j = 0; j < c - 1; ++j) {
        graph[r - 1][j] = graph[r - 1][j + 1];
    }
    for (int i = r - 1; i > down; --i) {
        graph[i][c - 1] = graph[i - 1][c - 1];
    }
    for (int j = c - 1; j > 1; --j) {
        graph[down][j] = graph[down][j - 1];
    }
    graph[down][1] = 0;

    graph[up][0] = -1;
    graph[down][0] = -1;
}

int main() {
    int R, C, T;
    cin >> R >> C >> T;

    int up = -1, down = -1;

    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            cin >> graph[i][j];
        }
    }

    for (int i = 0; i < R; ++i) {
        if (graph[i][0] == -1) {
            up = i;
            down = i + 1;
            break;
        }
    }

    for (int i = 0; i < T; ++i) {
        spread_graph(graph, R, C);
        air_purifier(up, down, graph, R, C);
    }

    int result = 0;
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            if (graph[i][j] > 0) {
                result += graph[i][j];
            }
        }
    }

    cout << result << '\n';

    return 0;
}