[BOJ] #17144 미세먼지 안녕!

시간 제한	메모리 제한	정답 비율
1 초	512 MB	54.847%

 

17144번: 미세먼지 안녕!

 

해결방안

미세먼지 확산하는 단계, 공기가 순환하는 단계를 나눠서 구현하였다.

먼저 미세먼지가 확산하는 단계에서 유의해야할 점이 있다. 한 번 미세먼지가 확산할 때는 이전 또는 초기의 미세먼지 수치에서 모든 값을 계산한 후 합산하는 단계를 거쳐야 한다. 따라서 배열을 arr와 tmp 두 개를 사용하여 arr에서 기존 미세먼지 수치를 알아냈고 tmp는 더해질 미세먼지 수를 저장해두어 마지막에 arr에 tmp 값을 더했다.

공기가 순환할 때는 for 문 7개를 통해서 값을 하나하나씩 밀었는데, 맞은 사람 코드를 보고 더 좋은 방법을 찾을 수 있었다.  해당 방법은 아래에 첨부

 

메모리	시간
2012 KB	40 ms

#include<iostream>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int, int> p;
int n, m, t, arr[55][55], tmp[55][55], ans; // t초 후 미세먼지의 양을 출력.
int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 };
vector<int> aircleaner;
void spread(int r, int c) {
    int& A = arr[r][c];
    int cnt = 0;
    for (int i = 0; i < 4; i++) {
        int nr = r + dx[i];     int nc = c + dy[i];
        if (arr[nr][nc] != -1 && nr >= 0 && nr < n && nc >= 0 && nc < m) {
            tmp[nr][nc] += (A / 5); cnt++;
        }
    }
    A -= (A / 5) * cnt;
}
int main() {
    scanf("%d%d%d", &n, &m, &t);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] == -1)aircleaner.push_back(i);
        }
    }
    while (t--) {
        // 미세먼지 확산
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] > 0) 
                    spread(i, j);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] += tmp[i][j];
            }
        }
        memset(tmp, 0, sizeof(tmp));
        // 공기 순환
        int row_ccw = aircleaner[0]; // counterclockwise
        int row_cw = aircleaner[1]; //clockwise
        for (int i = row_ccw - 1; i > 0; i--) {
            arr[i][0] = arr[i - 1][0];
        }
        for (int i = row_cw + 1; i < n - 1; i++) {
            arr[i][0] = arr[i + 1][0];
        }
        for (int j = 0; j < m - 1; j++) {
            arr[0][j] = arr[0][j + 1];
            arr[n - 1][j] = arr[n - 1][j + 1];
        }
        for (int i = 0; i < row_ccw; i++) {
            arr[i][m - 1] = arr[i + 1][m - 1];
        }
        for (int i = n - 1; i > row_cw; i--) {
            arr[i][m - 1] = arr[i - 1][m - 1];
        }
        for (int j = m - 1; j > 1; j--) {
            arr[row_ccw][j] = arr[row_ccw][j - 1];
        }    
        for (int j = m - 1; j > 1; j--) {
            arr[row_cw][j] = arr[row_cw][j - 1];
        }
        arr[row_ccw][1] = 0; arr[row_cw][1] = 0;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j] != -1)ans += arr[i][j];
        }
    }
    printf("%d", ans);
    return 0;
}

 

주의

memset 헤더를 지정안해줘서 한 번 컴파일 에러가 나왔다. 

memset을 쓸 때 string.h 헤더 잊지 않기!

 

memset 대신 쓸 수 있는 방법

while 문 안에 지역변수로

int tmp[55][55] = {0};

이와 같이 선언하면 memset 함수가 필요 없음.

 

for 문 더 간편하게 쓰기

#define F(x,y,u,p) for(int x=0; x<u; x++)for(int y=0;y<p;y++)

정의해두면 F(i, j, R, C) { } 로 이중포문을 돌릴 수 있다. 이 때 i와 j의 혼동이 적어져 실수를 줄일 수 있다.

 

배열 순환 더 쉽게 하기

int dd[4][2] = { {0,1},{-1,0},{0,-1},{1,0} }, dx[8] = { 0,1,2,3,0,3,2,1 };
 
for (int i = 0; i < 2; i++) {
    int cn = 0, cm = 0, ii = q[i][0], jj = q[i][1];
    while (1) {
        int ni = ii + dd[dx[cz]][0], nj = jj + dd[dx[cz]][1];
        if (ni == q[i][0] && nj == 0) { cz++; break; }
        if (chk(ni, nj)) { 
            cm = a[ni][nj]; 
            a[ni][nj] = cn; 
            cn = cm; 
            ii = ni; jj = nj; 
        }
        else cz++;
    }
}

내 코드에서 dx, dy 였던 배열을 합쳐 dd라는 이차원 배열로 저장시켜뒀고, 공기의 순환을 나타내기 위해 그 흐름대로 시계방향으로 도는 0,1,2,3 과 반 시계방향으로 도는 0,3,2,1 을 dx 배열에 저장시켜 dd[dx[cz]][0] 와 같은 방식으로 계속해서 더해가며 탐색할 수 있었다.