[BOJ] 백준 17144 미세먼지 안녕! c++ (시뮬레이션, 구현) - 삼성 SW 역량 테스트 기출 문제

문제 출처 : https://www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

---

풀이

미세먼지는 동시에 네 방향으로 확산하고 공기청정기는 미세먼지를 밀어내는 시뮬레이션이다.

여기서 핵심은 동시에 확산한다는 것이다. 이 부분을 못봐서 헤맸었다....

두번째는 공기청정기 위, 아래에 따라 밀어내는 방향이 다르다.

미세먼지 동시 확산

동시에 확산하는 것을 구하려면 어떻게 해야 할까?

바로 추후 한 번에 추가할 배열을 따로 선언하고, 거기에 각 계산 결과를 넣어두었다가 마지막에 초기 배열에 더해주는 것이다.

아래 코드를 보자.

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;
    }
}

공식에 따라 add 배열에 확산되는 부분, 남은 미세먼지를 저장한다.

각 과정이 모두 끝나면 한 번에 기존 배열에 연산해준다.

 

공기청정기 로직 구현

우선 문제 조건을 보자.

• 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
• 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
• 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

사진대로 위, 아래로 진행하는 것을 구분해야 한다.

 

필자는 아래 방법으로 구현하였다.

 

먼저 공기청정기 위는 0, 아래는 1로 매개변수를 넣어주어 구분한다.

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

 

사진을 보면 아래와 같이 꺾이는 포인트가 5개가 있다. (파랑 동그라미는 입력행(R)에따라 R, row-1로 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});

그 후 화살표대로 차례대로 진행하며 꺾이는 포인트에 도착한 경우 방향 전환을 해준다.

이때, 구분용도인 매개변수에 따라 어느 방향으로 갈지 구분한다.

공기청정기 위는 반시계, 아래는 시계방향으로 회전하므로 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;
}