[ 백준 17144 ] 미세먼지 안녕! (C++)

[문제보기]

 

[해결과정]

 1. 공기청정기 위치를 저장할 구조체 생성

 2. 기존 맵 1개, 기존 맵에서 먼지가 퍼지는 것을 저장할 맵 1개 생성

 3. input

 

 4. 기존 맵(map)을 돌며 먼지가 있으면 퍼지는 것을 저장할 맵(arr)에 계산 하여 저장

 5. 주변에 퍼질 수 있는 공간에 퍼뜨리고, 그 수를 별도 저장.

 6. 다 퍼뜨리고 해당 공간 계산

 

 7. map에 arr맵을 복사하고, arr맵 초기화.

 

 8. 위쪽 공기청정기, 아래쪽 공기청정기 순차적으로 수행

  (반시계 경우, 시계방향으로 가며 칸을 끌어당기기)

  (시계 경우, 반시계방향으로 가며 칸을 끌어당기기)

 

[소스코드]

#include<iostream>
#include<queue>
#include<math.h>
#include<memory.h>
#include<vector>
using namespace std;
const int MAX = 52;
 
int arr[MAX][MAX];
int map[MAX][MAX];
int n, m, t;
 
//공기청정기 위치
struct Coor {
    int y;
    int x;
};
Coor coor[2];
int c = 0;
 
// 4방향 탐색
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
bool inside(int y, int x) {
    return y >= 0 && y < n && x >= 0 && x < m;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m >> t;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            if (map[i][j] == -1) {
                coor[c].y = i;
                coor[c].x = j;
                c++;
            }
        }
    }
 
    while (t--) {
 
        // 1. 미세먼지 확산
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0 || map[i][j] == -1) continue;
 
                int cnt = 0;
                int ny, nx;
 
                for (int h = 0; h < 4; h++) {
                    ny = i + dy[h];
                    nx = j + dx[h];
                    if (ny == coor[0].y && nx == 0) continue;
                    if (ny == coor[1].y && nx == 0) continue;
                    if (inside(ny, nx)) {
                        cnt++;
                        double num = map[i][j] / 5.0;
                        arr[ny][nx] += (int)num;
                    }
                }
                arr[i][j] += map[i][j] - (map[i][j] / 5) * cnt;
 
            
            }
        }
 
        memset(map, 0, sizeof(map));
        memcpy(map, arr, sizeof(map));
        memset(arr, 0, sizeof(arr));
        
        // 2. 공기청정기 작동
            //첫번째 공기청정기 (반시계 방향)
 
        //위쪽 공기청정기가 윗 벽에 붙어 있지 않다면..
        int air1 = coor[0].y;
        if (air1 != 0) {
            for (int a = air1 - 1; a > 0; a--) {
                map[a][0] = map[a - 1][0];
            }
        }
 
        for (int a = 0; a < m-1; a++) {
            map[0][a] = map[0][a + 1];
        }
 
        for (int a = 0; a < air1; a++) {
            map[a][m-1] = map[a+1][m-1];
        }
 
        for (int a = m - 1; a > 0; a--) {
            map[air1][a] = map[air1][a-1];
        }
 
            //두번째 공기청정기 (시계 방향)
        
        //아래쪽 공기청정기가 아랫 벽에 붙어 있지 않다면..
        int air2 = coor[1].y;
        if (air2 != n - 1) {
            for (int a = air2 + 1; a < n - 1; a++) {
                map[a][0] = map[a+1][0];
            }
        }
 
        for (int a = 0; a < m - 1; a++) {
            map[n - 1][a] = map[n - 1][a + 1];
        }
 
        for (int a = n - 1; a > air2; a--) {
            map[a][m - 1] = map[a - 1][m - 1];
        }
 
        for (int a = m - 1; a > 0; a--) {
            map[air2][a] = map[air2][a - 1];
        }
        
        map[air1][1] = 0;
        map[air2][1] = 0;
 
    
    }
 
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] != -1) ans += map[i][j];
        }
    }
 
    cout << ans << "\n";
 
 
 
    return 0;
}

 

[해결 과정 중 실수한 부분 / 잡담]

 삼성 문제 중 시뮬레이션 문제다. 이 문제의 핵심은, 시계 혹은 반시계 방향으로 칸을 끌어당기는 것이다. 이 문제 이후로 이렇게 맵을 돌리는 경우의 문제가 더 심화되어 출제되었던 것 같다.

 

 시키는대로 진행해서 큰 어려움은 없었지만, 조금 헤깔리며 긴가민가 했다. 그래서 디버깅을 많이 하면서 풀었고, 58분 소요됐다.

 

[관련 문제 혹은 비슷한 문제]

 삼성 기출