BOJ 17144 - 미세먼지 안녕

www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

 

두가지를 구현해야한다.

1. 미세먼지를 퍼트리는 함수

2. 공기청정기를 가동하는 함수

 

미세먼지를 퍼트리는 함수는 

공기청정기가 있는지역 또는 2차원배열 범위를 벗어나는 지역을 제외하고 전부 퍼질수 있다.

주의할점은 이미 미세먼지가 존재하는 지역에 미세먼지가 퍼질때이다.

 

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

위 그림에서 왼쪽이 미세먼지가 퍼지기 전이고

오른쪽이 퍼진 이후다.

 

먼저 (0, 1) 부분 (값 30) 이 퍼질때는 30 / 5 = 6 이 퍼져야한다

그리고 30과 인접한 세부분 (0, 0), (0, 2), (1, 1) 은 배열의 범위를 벗어나는 지역도 아니며

공기청정기가 있는 지역도 아니므로, 퍼질 수 있다.

그래서 30이 퍼질때는 아래와 같이 퍼질 것이다.

0 + 6	12	7 + 6
-1	10 + 6	0
-1	0	20

이렇게 퍼지는게 맞긴 하나, 주의할게 하나있다면,

(1, 1) 과 (0, 2) 는 원래 값이 10 과 7 이었다.

(0, 1) 을 퍼트린 이후, (0, 2) 와 (1, 1) 을 퍼트릴때, 퍼트리는 값이 14, 16으로 퍼지는게 아니라

7, 10 으로 퍼져야한다.

즉 원래 값으로 퍼져야한다는 뜻이다.

 

그래서 별도의 복사본 이차원배열을 만들고 (copy_map[MAX][MAX]) 

복사본의 값을 바꾸도록 해야한다.

 

공기청정기를 가동하는 함수는 문제의 설명대로

공기청정기 윗부분은 오른쪽 -> 위쪽 -> 왼쪽 -> 아래쪽 순서로 한칸씩 이동하게 했다.

공기청정기 아랫부분은 오른쪽 -> 아래쪽 -> 왼쪽 -> 위쪽 순서로 한칸씩 이동하게 했다.

 

여기서 주의할점은 오른쪽으로 이동할때, 이동하기 위한 반복문을 수행하기 전에

시작부분을 0으로 만들고 시작해줘야한다.

map[y][x + 1] = 0;
for (int j = x + 1; j < C - 1; ++j) map[y][j + 1] = copy_map[y][j];

 

나같은 경우는 논리가 꼬여서 그런지 몰라도

복사를 두번했다.

1. 원본을 복사본에 두는 복사

2. 복사본을 원본에 두는 복사

이렇게 두번해야했다.

 

2번을 한 것은 공기청정기 가동시 미세먼지의 이동을 표현하기 위해서

한칸씩 뒤로 물려야하는데, 배열하나로는 표현할수 없기 때문이었다.

 

 

- c++

#include <algorithm>
#include <iostream>
#include <vector>
 
#define MAX 51
 
using namespace std;
 
int map[MAX][MAX], copy_map[MAX][MAX];
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1}; 
vector<pair<int, int>> aircon_pos;
int R, C, T, answer;
 
void map_copy() {
    for (int i = 0; i < R; ++i) 
        for (int j = 0; j < C; ++j)
            copy_map[i][j] = map[i][j];
}
 
void map_copy2() {
    for (int i = 0; i < R; ++i)
        for (int j = 0; j < C; ++j)
            map[i][j] = copy_map[i][j];
} 
 
int count_dust() {
    int cnt = 0;
    for (int i = 0; i < R; ++i)
        for (int j = 0; j < C; ++j)
            if (map[i][j] > 0)
                cnt += map[i][j];
    return cnt;
}
 
void turn_on_air_purifier() {
    for (int i = 0; i < 2; ++i) {
        int y = aircon_pos[i].first, x = aircon_pos[i].second; 
        if (i == 0) {
            // move right
            map[y][x + 1] = 0;
            for (int j = x + 1; j < C - 1; ++j) map[y][j + 1] = copy_map[y][j];
            
            // move top
            for (int j = y - 1; j >= 0; --j) map[j][C - 1] = copy_map[j + 1][C - 1];    
    
            // move left
            for (int j = C - 2; j >= 0; --j) map[0][j] = copy_map[0][j + 1];
            
            // move down
            for (int j = 1; j < y; ++j) map[j][0] = copy_map[j - 1][0];
        } else if (i == 1) {
            // move right
            map[y][x + 1] = 0;
            for (int j = x + 1; j < C - 1; ++j) map[y][j + 1] = copy_map[y][j];
            
            // move down
            for (int j = y + 1; j < R; ++j) map[j][C - 1] = copy_map[j - 1][C - 1];
    
            // move left
            for (int j = C - 2; j >= 0; --j) map[R - 1][j] = copy_map[R - 1][j + 1];
            
            // move top
            for (int j = R - 2; j > y; --j) map[j][0] = copy_map[j + 1][0];
        }
    }
}
 
void spread_dust() {
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            if (map[i][j] > 0) {
                int temp =  map[i][j] / 5, count_spread;
                vector<pair<int, int>> vec;
                for (int k = 0; k < 4; ++k) {
                    int ny = i + dy[k], nx = j + dx[k];
                    if (ny < 0 || ny >= R || nx < 0 || nx >= C || map[ny][nx] == -1) continue;
                    vec.push_back({ny, nx});
                }
                
                count_spread = vec.size();
                for (int k = 0; k < count_spread; ++k) {
                    int ny = vec[k].first, nx = vec[k].second;
                    copy_map[ny][nx] += temp;
                }
                copy_map[i][j] = copy_map[i][j] - temp * count_spread;
            }
        }
    }
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> R >> C >> T;
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            cin >> map[i][j];
            if (map[i][j] == -1) aircon_pos.push_back({i, j});
        }
    }
    
    while(T--) {
        map_copy();
        spread_dust();
        map_copy2();
        turn_on_air_purifier();
    }
        
    answer = count_dust();
    cout << answer;
    
    return 0;
}

 

 

 

 

 

삼성 기출문제는 문제푸는 시간이 너무 오래걸린다

푸는 시간을 줄여야하는데 언제쯤 줄어들지 기미가 안보인다.