BOJ 17144 · 미세먼지 안녕!

알고리즘 분류 : 시뮬레이션  

문제에 주어진 조건을 그대로 구현하는 문제다. 크게 두 단계로 나눠서 설계해야 한다. 첫 번째, 미세먼지가 확산되는 과정, 두 번째 공기청정기의 바람이 순환하는 과정이다.

• 1. 모든 미세먼지는 5 이상의 양이 남아있으면, 상하좌우로 확산할 수 있다.
• 확산할 때 상하좌우에 이미 먼지가 있는 경우가 있으므로, 별도의 배열을 만들어서 확산되는 먼지의 양을 저장해야 한다. 값을 바로 업데이트하면 다음 먼지 확산에 영향을 주기 때문에, 이 과정이 필요하다.
• 현재 먼지의 양을 5로 나눈 후, 그 양을 상하좌우 칸에 더한다. 위에서 만든 별도의 배열 B에 더한다.
• 모든 과정이 끝나면, 원래 먼지 배열 A에 확산 배열 B 값을 업데이트한다.

• 2. 미세먼지가 바람 방향에 따라 순환한다.
• 입력받을 때 공기청정기의 위치를 S1, S2에 저장한다. 
• 위쪽 공기청정기는 S1을 기준으로 반시계 방향으로 회전한다.
• 아래쪽 공기청정기는 S2를 기준으로 시계 방향으로 회전한다.
• 역순으로 회전하면서, 현재 값에 다음 값을 저장하면 된다.

---

C++ 소스코드

#include <cstdio>
#include <cstring>

struct air {
    int x, y;
};

int r, c, t, s1=-1, s2, ans;
int a[50][50];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};


void diffuse() {
    int b[50][50] = {0};
    memcpy(b, a, sizeof(a));
    for (int i=0; i<r; i++) {
        for (int j=0; j<c; j++) {
            if (a[i][j] >= 5) {
                int d = a[i][j]/5;
                for (int k=0; k<4; k++) {
                    int ni = i+dx[k], nj = j+dy[k];
                    if (0 <= ni && ni < r && 0 <= nj && nj < c && a[ni][nj] != -1) {
                        b[ni][nj] += d;
                        b[i][j] -= d;
                    }
                }
            }
        }
    }
    memcpy(a, b, sizeof(b));
}

void purify() {
    // Top purifier
    for (int i=s1-2; i>=0; i--) a[i+1][0] = a[i][0];  // ↓
    for (int i=0; i<c-1; i++) a[0][i] = a[0][i+1];    // ←
    for (int i=0; i<s1; i++) a[i][c-1] = a[i+1][c-1]; // ↑
    for (int i=c-2; i>=0; i--) a[s1][i+1] = a[s1][i]; // →
    a[s1][1] = 0;
    // Bottom purifier
    for (int i=s2+1; i<r-1; i++) a[i][0] = a[i+1][0];   // ↑
    for (int i=0; i<c-1; i++) a[r-1][i] = a[r-1][i+1];  // ←
    for (int i=r-2; i>=s2; i--) a[i+1][c-1] = a[i][c-1];// ↓
    for (int i=c-2; i>=0; i--) a[s2][i+1] = a[s2][i];   // →
    a[s2][1] = 0;
}

void solve() {
    while (t--) {
        diffuse();
        purify();
    }
    for (int i=0; i<r; i++) {
        for (int j=0; j<c; j++) {
            if (a[i][j] > 0) {
                ans += a[i][j];
            }
        }
    }
    printf("%d\n", ans);
}

int main() {
    scanf("%d %d %d", &r, &c, &t);
    for (int i=0; i<r; i++) {
        for (int j=0; j<c; j++) {
            scanf("%d", &a[i][j]);
            if (a[i][j] == -1) {
                // s1 (top), s2 (bottom)
                if (s1 == -1) s1 = i;
                else s2 = i;
            }
        }
    }
    solve();
    return 0;
}

---

Python 3 소스코드

r, c, t = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(r)]
s1, s2 = -1, 0

def diffuse():
    global a
    b = [[0]*c for _ in range(r)]
    for i in range(r):
        for j in range(c):
            if a[i][j] >= 5:
                d = a[i][j]//5
                for dx, dy in (-1,0), (1,0), (0,1), (0,-1):
                    ni, nj = i+dx, j+dy
                    if 0 <= ni < r and 0 <= nj < c and a[ni][nj] != -1:
                        b[ni][nj] += d
                        a[i][j] -= d
    for i in range(r):
        for j in range(c):
            a[i][j] += b[i][j]

def purify():
    for i in range(s1-2, -1, -1):
        a[i+1][0] = a[i][0]
    for i in range(c-1):
        a[0][i] = a[0][i+1]
    for i in range(s1):
        a[i][c-1] = a[i+1][c-1]
    for i in range(c-2, -1, -1):
        a[s1][i+1] = a[s1][i]
    a[s1][1] = 0
    for i in range(s2+1, r-1):
        a[i][0] = a[i+1][0]
    for i in range(c-1):
        a[r-1][i] = a[r-1][i+1]
    for i in range(r-2, s2-1, -1):
        a[i+1][c-1] = a[i][c-1]
    for i in range(c-2, -1, -1):
        a[s2][i+1] = a[s2][i]
    a[s2][1] = 0

def solve():
    for _ in range(t):
        diffuse()
        purify()
    print(sum(map(sum, a))+2)

for i in range(r):
    for j in range(c):
        if a[i][j] == -1:
            if s1 == -1:
                s1 = i
            else:
                s2 = i
solve()

---

참고

• 백준 온라인 저지 : BOJ 17144