[백준][구현] 17144 미세먼지 안녕! c++구현

목차

1. 문제
2. 문제 구현 방향
3. 코드 구현
4. 공기 청정기 재구현 방향

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

문제

 

문제 구현 방향

너무 복잡하게 푼 것 같다...

공기 청정기 구현 방향을 좀만 더 생각했으면 미리 움직일 좌표들을 저장해 놓고 

순차적으로 당기는 방식으로 효율적으로 구현했으면 좋았을 것 같다..

 

 

코드 구현

cpp

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<map>
#include<queue>
#include<math.h>

using namespace std;


int R, C, T;
int board[100][100] = { 0 };
int Sboard[100][100] = { 0 };
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1, -1, 0, 0 };
int start1 = -1, start2=-1;

//배열 원복 복제
void duplicating() {
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            board[i][j] = Sboard[i][j];
        }
    }
    fill(&Sboard[0][0], &Sboard[0][0] + 100 * 100, 0);
}

//카운팅
int counting() {
    int cnt = 0;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cnt += board[i][j];
        }
    }
    return cnt;
}

//먼지의 확산
void dustMoving() {
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (board[i][j] != -1 && board[i][j] != 0) {
                int cnt = 0;
                for (int p = 0; p < 4; p++) {
                    int nx = j + dx[p];
                    int ny = i + dy[p];
                    if (nx < 0 || nx > C - 1 || ny < 0 || ny > R - 1)
                        continue;
                    if (board[ny][nx] == -1)
                        continue;
                    Sboard[ny][nx] += board[i][j] / 5;
                    cnt++;
                }
                Sboard[i][j] += board[i][j] - (board[i][j] / 5) * cnt;
            }
        }
    }
}

//공기 청정기 확산
void cleanMoving() {
    //위쪽 공기 청정기
    int sx = C-1;
    int sy = start1;
    int save = Sboard[sy][sx];
    while (true) {
        int d = sx - 1;
        if (d < 0)
            break;
        Sboard[sy][sx] = Sboard[sy][d];
        sx--;
    }
   
    sx = C - 1;
    sy = 0;
    int save2 = Sboard[sy][sx];
    while (true) {
        int d = sy +1;
        if (d  > start1)
            break;
        if (d == start1) 
            Sboard[sy][sx] = save;
        else 
            Sboard[sy][sx] = Sboard[d][sx];

        sy++;
    }

    sy = 0;
    sx = 0;
    save = Sboard[sy][sx];
    while (true) {
        int d = sx + 1;
        if (d > C-1)
            break;
        if (d == C - 1)
            Sboard[sy][sx] = save2;
        else
            Sboard[sy][sx] = Sboard[sy][d];

        sx++;
    }

    sx = 0;
    sy = start1;
    save2 = Sboard[sy][sx];
    while (true) {
        int d = sy -1;
        if (d <0)
            break;
        if (d == 0)
            Sboard[sy][sx] = save;
        else
            Sboard[sy][sx] = Sboard[d][sx];
        sy--;
    }

    Sboard[start1][0] = -1;


    //아래쪽 공기 청정기
     sx = C-1;
     sy = start2;
     save = Sboard[sy][sx];
     while (true) {
         int d = sx - 1;
         if (d < 0)
             break;
         Sboard[sy][sx] = Sboard[sy][d];
         sx--;
     }
     sx = C - 1;
     sy = R-1;
     save2 = Sboard[sy][sx];
     while (true) {
         int d = sy - 1;
         if (d < start2)
             break;
         if (d == start2)
             Sboard[sy][sx] = save;
         else
             Sboard[sy][sx] = Sboard[d][sx];
         sy--;
     }
     sy = R - 1;
     sx = 0;
     save = Sboard[sy][sx];
     while (true) {
         int d = sx +1;
         if (d > C-1)
             break;
         if (d == C - 1)
             Sboard[sy][sx] = save2;
         else
             Sboard[sy][sx] = Sboard[sy][d];
         sx++;
     }

     save2 = Sboard[sy][sx];
     sx = 0;
     sy = start2;
     while (true) {
         int d = sy + 1;
         if (d > R-1)
             break;
         if (d == R - 1)
             Sboard[sy][sx] = save;
         else
             Sboard[sy][sx] = Sboard[d][sx];
         sy++;
     }
     Sboard[start2][0] = -1;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> R >> C >> T;
    int day = 0;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> board[i][j];
            if (board[i][j] == -1) {
                if (start1 == -1)
                    start1 = i;
                else
                    start2 = i;
            }
        
        }
    }
    while (day < T) { 
        //1. 미세먼지의 확산
        dustMoving();
        //2. 공기청정기 확산
        cleanMoving();
        //다시 옮기기
 
        //다시 복제하기
        duplicating();
        day++;
    }

    //-1제외해주어야 하므로 2더함
    cout << counting()+2;



}

 

 

공기 청정기 재구현 방향

이런식으로 구현하면 훨씬 더 간결하고 쉽게 구현 가능하다.

cpp

vector<pair<int, int>> chung(int sy, int sx, int dy[], int dx[]){   
    vector<pair<int, int>> v; 
    int cnt = 0; 
    int y = sy; 
    int x = sx;
    while(true){ 
        int ny = y + dy[cnt];
        int nx = x + dx[cnt];  
        if(ny == sy && nx == sx)break;
        if(ny < 0 || ny >= n || nx < 0 || nx >= m){
            cnt++; 
            ny = y + dy[cnt];
            nx = x + dx[cnt];
        } 
        if(ny == sy && nx == sx)break;
        y = ny; x = nx; 
        v.push_back({ny, nx});
    }
    return v;
} 
void go(vector<pair<int, int>> &v){  
    for(int i = v.size() - 1; i > 0; i--){
        a[v[i].first][v[i].second] = a[v[i - 1].first][v[i - 1].second];
    } 
    a[v[0].first][v[0].second] = 0; 
    return;
}