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

출처는 아래와 같다. 2019년 삼성 상반기 기출문제로 알고있다.

 

acmicpc.net/problem/17144

 

이 문제 역시 시키는대로 구현하면 되는 문제이다. 문제는 구현이 누군가에게는 쉬울수도 어려울수도 있다는 것이 문제이다. 

 

문제를 보면 2가지로 나누어 순서대로 구현하여 문제를 해결하면 된다. 순서대로 확인해보자.

 

1) 확산

미세먼지가 확산된다는데 그냥 읽어서는 정확하게 구현하기 쉽지 않다. 필자는 예제에 있는 그림 중 3번째 그림을 보면서 이해하는데 시간이 좀 걸렸다. 이것을 코딩하는데 생각하는것도 만만치 않을텐데 필자는 나눠줘서 확산되는 값들을 저장하는 f[][] 배열을 통해 구현하였다.

f[][] 배열은 확산에 따른 모든 값들을 더해지게 되고 원본 배열은 arr[][]에는 정 중앙의 확산에 의해 값이 줄어드는 값만을 갱신하여 매 초마다 확산을 구현하였다.  

 

void flatter(int a,int b) {
    int cnt = 0;
    for (int i = 0; i < 4; i++) {
        int kx = a + dx[i];
        int ky = b + dy[i];
        if (kx >= 0 && kx < r && ky >= 0 && ky < c && arr[kx][ky] != -1) {
            f[kx][ky] = f[kx][ky]+ (arr[a][b] / 5);
            cnt++;
        }
    }
    arr[a][b] = arr[a][b] - arr[a][b] / 5 * cnt;
}

 

코드를 하면 위와 같다. 이것을 나중에 원본 배열인 arr[][]에 다 더해준다. 전체 코드를 참고바란다.

 

 

2) 회전

회전은.. 구현을 도통하다 필자도 참고하였다. 4개의 반복문을 통해 코드를 참고하여 작성하였다. 이걸 봤을때 앞으로 회전 구현에 있어 어떤 기준을 잡으면 그 기준이 받아오는 순서대로 작성하면 조금이나마 쉽게 이해할수 있다. 예를 들면 아래와 같다.

 

 

위 그림에서 아래방향 -> 좌측방향 -> 위방향 -> 우측방향 순으로 끝 점을 제외하여 작성해주면 조금이나마 쉽게 이해하여 코딩할 수 있다.

 

 

전체코드는 아래와 같다.

 

#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<math.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iterator>
#include<deque>
#include<sstream>
#pragma warning(disable:4996)
using namespace std;
 
int r, c, t,r1,r2,rr1,rr2,ans;
int arr[51][51], f[51][51],dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
 
void flatter(int a,int b) {
    int cnt = 0;
    for (int i = 0; i < 4; i++) {
        int kx = a + dx[i];
        int ky = b + dy[i];
        if (kx >= 0 && kx < r && ky >= 0 && ky < c && arr[kx][ky] != -1) {
            f[kx][ky] = f[kx][ky]+ (arr[a][b] / 5);
            cnt++;
        }
    }
    arr[a][b] = arr[a][b] - arr[a][b] / 5 * cnt;
}
 
void rotate(int a,int b) {
    for (int i = a - 1; i >= 1; i--) arr[i][0] = arr[i - 1][0]; // 아래방향
    for (int i = 0; i < c - 1; i++) arr[0][i] = arr[0][i + 1]; // <<<
    for (int i = 0; i < a; i++) arr[i][c - 1] = arr[i + 1][c - 1]; //윗방향
    for (int i = c - 1; i >= 1; i--) arr[a][i] = arr[a][i - 1]; // >>>>
    arr[a][1] = 0;
}
 
void rotate2(int a, int b) {
    for (int i = a + 1; i < r - 1; i++) arr[i][0] = arr[i + 1][0]; //윗방향
    for (int i = 0; i < c - 1; i++) arr[r - 1][i] = arr[r - 1][i + 1]; //<<<<
    for (int i = r-1; i > a; i--) arr[i][c - 1] = arr[i - 1][c - 1]; // 아래방향
    for (int i = c - 1; i >= 1; i--) arr[a][i] = arr[a][i - 1];  // >>>>>
    arr[a][1] = 0;
}
 
int main()
{
    int chk = 0;
    cin >> r >> c >> t;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] == -1 && chk == 0) r1 = i, r2 = j, chk = 1;
            else if (arr[i][j] == -1 && chk == 1) rr1 = i, rr2 = j;
        }
    }
    while (t--) {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (arr[i][j] > 0) {
                    flatter(i, j);
                }
            }
        }
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                arr[i][j] = arr[i][j] + f[i][j];
                //printf("%d ", arr[i][j]);
            }
            //printf("\n");
        }
        rotate(r1, r2);
        rotate2(rr1, rr2);
        memset(f, 0, sizeof(f));
        //printf("\n\n");
        //for (int i = 0; i < r; i++) {
            //for (int j = 0; j < c; j++) {
                //printf("%d ", arr[i][j]);
            //}
            //printf("\n");
        //}
        //cout << r1 << r2 << rr1 << rr2;
    }
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (arr[i][j] >= 0) ans = ans + arr[i][j];
        }
    }
    printf("%d", ans);
    return 0;
}