(BOJ) 백준 17144 굿바이 미세먼지! c++ (시뮬레이션, 구현) – 삼성SW능력시험의 문제점

by

문제 소스: https://www.acmicpc.net/problem/17144

17144호: 입자상 물질 안녕하세요!

미세먼지를 제거하기 위해 오래된 사과는 공기청정기를 설치하려고 합니다. 공기청정기의 성능을 테스트하기 위해 오래된 사과집을 1×1 셀로 나눈 R×C 크기의 그리드로 표현했습니다. 사용

www.acmicpc.net


설명

미세먼지는 동시에 4방향으로 퍼지고 공기청정기는 미세먼지를 내뿜는 시뮬레이션이다.

여기서 핵심은 동시에 확산이 부분을 보고 넋을 잃었습니다…

두 번째는 공기청정기의 상단과 하단에 따라 추력 방향이 다릅니다.

미세먼지 동시 확산

동시에 확산되게 하려면 어떻게 해야 합니까?

나중에 추가할 배열 선언각 계산의 결과를 거기에 넣고 마지막에 초기 배열에 추가하십시오.

아래 코드를 살펴보겠습니다.

int arr(51)(51);
int add(51)(51); // 한번에 더해줄 배열

for(int i = 0; i < R; i++){
    for(int j = 0; j < C; j++){
        if(arr(i)(j) <= 0) continue;
        int cnt = 0;
        for(int k = 0; k < 4; k++){
            int nrow = i + dy(k);
            int ncol = j + dx(k);
            if(nrow < 0 || nrow >= R || ncol < 0 || ncol >= C || arr(nrow)(ncol) == -1) continue;

            cnt++; // 확산된 방향 개수
            add(nrow)(ncol) += (arr(i)(j) / 5);
        }
        add(i)(j) -= ((arr(i)(j) / 5) * cnt);
    }
}
// 마지막에 한 번에 연산
for(int i = 0; i < R; i++){
    for(int j = 0; j < C; j++){
        arr(i)(j) += add(i)(j);
        add(i)(j) = 0;
    }
}

공식에 따르면 확산된 부분과 남은 입자상 물질을 추가 어레이에 저장하다.

각 작업이 완료되면 기존 어레이가 즉시 처리됩니다.

에어클리너 로직 구현

먼저 문제 조건을 살펴보겠습니다.

  • 상부 공기 청정기의 바람은 반시계 방향으로 순환하고 하부 공기 청정기의 바람은 시계 방향으로 순환합니다.
  • 바람이 불면 미세먼지가 바람을 타고 하나씩 이동한다.
  • 공기청정기에서 불어오는 바람은 미립자 물질이 없는 바람이며, 공기청정기로 들어오는 미립자 물질은 모두 청소합니다.


그림과 같이 상승과 하강을 구분해야 합니다.

다음과 같이 구현했습니다.

먼저 공기청정기의 윗부분은 0, 아랫부분은 1이다.

void work_cleaner(int num){ // 0 위 1 아래
    int row = cleaner(num);
    ...    
}

아래 사진을 보시면 5개의 벤딩 포인트있습니다.


이 벤드 포인트를 저장합니다.

vector<pair<int, int>> endpoint;
endpoint.push_back({row, C-1});
endpoint.push_back({0, C-1});
endpoint.push_back({R-1, C-1});
endpoint.push_back({R-1, 0});
endpoint.push_back({0, 0});

그런 다음 화살표로 표시된 순서대로 진행하십시오. 전환점에 도달하면 방향을 바꾸십시오.하다

이때 분류 목적은 파라미터에 따라 어느 방향으로 가야할지 구분하다.

공기 청정기 위쪽은 시계 반대 방향으로 회전하고 아래쪽은 시계 방향으로 회전합니다.왜냐하면 dx, dy를 선언하고 매개변수에 따라 액세스 idx를 분류합니다.할 수 있어요.

int dx(4) = {1, 0, -1, 0}; // 우 하 좌 상(시계)
int dy(4) = {0, 1, 0, -1};

int idx = 0; // 방향 조절 idx(처음에 위, 아래 모두 오른쪽으로 가므로 0)
pair<int, int> now = {row, 1}; // 공기청정기 첫 시작 점

// 끝점이면 방향전환
for(int i = 0; i < endpoint.size(); i++){
    if(now == endpoint(i)) // 끝점인 경우
        num == 0 ? idx = (idx + 3) % 4 : idx = (idx + 1) % 4;
        // 위인경우 dx, dy idx를 하나씩 빼주면 반시계로 회전한다. (우 상 좌 하)
        // 아래인경우 dx, dy idx를 하나씩 더해주면 반시계로 회전한다. (우 하 좌 상)
}

그 과정에서 이전 값을 옮기면 공기청정기에 대한 최종 코드는 다음과 같다.

void work_cleaner(int num){
    int row = cleaner(num);
    int idx = 0; // 방향 조절 idx

    pair<int, int> now = {row, 1};
    vector<pair<int, int>> endpoint;
    endpoint.push_back({row, C-1});
    endpoint.push_back({0, C-1});
    endpoint.push_back({R-1, C-1});
    endpoint.push_back({R-1, 0});
    endpoint.push_back({0, 0});

    int pre = 0, tmp = 0;
    while(now.second != 0 || now.first != row){
        tmp = arr(now.first)(now.second);
        arr(now.first)(now.second) = pre;
        pre = tmp;

        // 끝점이면 방향전환
        for(int i = 0; i < endpoint.size(); i++){
            if(now == endpoint(i))
                num == 0 ? idx = (idx + 3) % 4 : idx = (idx + 1) % 4;
        }

        now.second += dx(idx);
        now.first += dy(idx);
    }
}

암호

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int R, C, T;
int arr(51)(51);
int add(51)(51); // 한번에 더해줄 배열
vector<int> cleaner;
int ans;

int dx(4) = {1, 0, -1, 0}; // 우 하 좌 상(시계)
int dy(4) = {0, 1, 0, -1};

void get_dust(){
    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            if(arr(i)(j) <= 0) continue;
            ans += arr(i)(j);
        }
    }
}

void work_cleaner(int num){
    int row = cleaner(num);
    int idx = 0; // 방향 조절 idx

    pair<int, int> now = {row, 1};
    vector<pair<int, int>> endpoint;
    endpoint.push_back({row, C-1});
    endpoint.push_back({0, C-1});
    endpoint.push_back({R-1, C-1});
    endpoint.push_back({R-1, 0});
    endpoint.push_back({0, 0});

    int pre = 0, tmp = 0;
    while(now.second != 0 || now.first != row){
        tmp = arr(now.first)(now.second);
        arr(now.first)(now.second) = pre;
        pre = tmp;

        // 끝점이면 방향전환
        for(int i = 0; i < endpoint.size(); i++){
            if(now == endpoint(i))
                num == 0 ? idx = (idx + 3) % 4 : idx = (idx + 1) % 4;
        }

        now.second += dx(idx);
        now.first += dy(idx);
    }
}

void solution(int time){
    if(T == time){
        get_dust();
        return;
    }

    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            if(arr(i)(j) <= 0) continue;
            int cnt = 0;
            for(int k = 0; k < 4; k++){
                int nrow = i + dy(k);
                int ncol = j + dx(k);
                if(nrow < 0 || nrow >= R || ncol < 0 || ncol >= C || arr(nrow)(ncol) == -1) continue;

                cnt++;
                add(nrow)(ncol) += (arr(i)(j) / 5);
            }
            add(i)(j) -= ((arr(i)(j) / 5) * cnt);
        }
    }

    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            arr(i)(j) += add(i)(j);
            add(i)(j) = 0;
        }
    }

    work_cleaner(0); // 위 작동
    work_cleaner(1); // 아래 작동

    solution(time+1);
    return;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> R >> C >> T;

    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            cin >> arr(i)(j);
            if(arr(i)(j) == -1)
                cleaner.push_back(i);
        }
    }
    solution(0);
    cout << ans << '\n';

    return 0;
}