[삼성기출]미세먼지...시뮬+탐색

일단 상반기 시험에도 멘붕이 왔었던 문제다 ..

그때의 문제는 일단 상하좌우 인접한 것만 보고 bfs에 꽂혀서 바로 bfs를 구현해버렸다.

그리고 나서 돌렸더니만 문제점이 초 단위로 탐색을 진행하는거여서 bfs는 인접하면 쭈루룩 진행되서 초단위로

실행시킬수가 없었다. 지금 생각해보니 백준 빙산 문제도 년단위로 진행되는 문제였었는데 좀 비슷한거같다...

오히려 빙산보다 쉬웠는데 빙신같이 못풀었다. ㅠㅠ. 그래서 bfs에서 조건으로 해결하려고 조건만 1시간동안 수정했었는

듯...2번문제는 생각보다 쉬웠는데 1번에서 멘붕와서 시간 다날려서 망했었다....

그리고 문제를 자세히 읽어보면, 넓이탐색을 하는것도 아니다.. 그냥 단순히 상하좌우만 탐색할 뿐... queue조차 필요없다

그리고 멘붕왔던 것은 전부다 동시에 확산이 되는것에서 멘붕이 왔었다.. 이미 확산이 되면 데이터가 달라져있는데 

어떻게 동시에 확산이 되느냐 생각하고 멘붕이 오다가 끝날때쯤에야 clone이 생각났다....

빙산에서도 마찬가지로 데이터가 값이 달라져서 문제가 생기는 경우에는 기본 데이터를 복사해서 복사한 데이터를 if문

조건으로 사용해주면 되는것을 ... ㅠㅠ 

그래도 얻은 교훈은 문제를 천천히 읽고 딱 맞는 방법을 생각해야된다. .. 

이번에는 문제를 읽자마자 그냥 이중포문돌면서 상하좌우로 한번 탐색해주면 되겠다고 생각했다.

그리고 미리 복사를 통해 그 데이터를 기준으로 확산을 시켜주면 된다고 생각했다.

그리고 나서는, 시뮬레이션적인 요소가 섞였는데 공기청정기이다.

shift방법을 이용해야하나 싶었지만 공기청정기로 사라져 버리는 데이터가 있어서 그냥 단순하게 옮겨주기만 하면됐다.

그러나 for문을 4번사용해야되는 까다로움과 인덱스를 잘 입력해주어야하는 까다로움이 있었다. 실수하기 딱 좋음.

탐색+시뮬레이션 적인 요소가 섞인 문제고 이러한 기출문제를 삼성이 좋아하는것 같다..

 

문제

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

1초 동안 아래 적힌 일이 순서대로 일어난다.

1. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
   • (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
   • 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
   • 확산되는 양은 Ar,c/5이고 소수점은 버린다.
   • (r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.
2. 공기청정기가 작동한다.
   • 공기청정기에서는 바람이 나온다.
   • 위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
   • 바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
   • 공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

다음은 확산의 예시이다.

왼쪽과 오른쪽에 칸이 없기 때문에, 두 방향으로만 확산이 일어났다.

인접한 네 방향으로 모두 확산이 일어난다.

공기청정기가 있는 칸으로는 확산이 일어나지 않는다.

공기청정기의 바람은 다음과 같은 방향으로 순환한다.

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

입력

첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.

둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

출력

첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

예제 입력 1 복사

7 8 1 0 0 0 0 0 0 0 9 0 0 0 0 3 0 0 8 -1 0 5 0 0 0 22 0 -1 8 0 0 0 0 0 0 0 0 0 0 0 10 43 0 0 0 5 0 15 0 0 0 0 0 40 0 0 0 20 0

예제 출력 1 복사

188

미세먼지의 확산이 일어나면 다음과 같은 상태가 된다. 

공기청정기가 작동한 이후 상태는 아래와 같다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;
 
int R, C, T, sum=2;
int dx[] = {1,-1,0,0}; //상하좌우
int dy[] = {0,0,-1,1};
 
int Air_row; //[Air_row-1][0],[Air_row][0] 에 청정기
vector<vector<int> > map(51,vector<int>(51));
 
void Show() {
    //cout << "Show the map\n";
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            sum += map[i][j];
        }
    }
    cout << sum << endl;
}
 
void diffusion() {
    vector<vector<int> > copymap = map; // 원래 맵이 copymap(사실핵심,데이터보존)
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            if (copymap[r][c] == 0 || copymap[r][c]==-1 ||copymap[r][c]<5) continue; //예외조건
 
            int howmuch = int(copymap[r][c] / 5); //확산량
            for (int k = 0; k < 4; k++) { //상하좌우로
                int rr = r + dx[k];
                int cc = c + dy[k];
                if (rr < 0 || rr >= R || cc < 0 || cc >= C || copymap[rr][cc]==-1) continue; //범위체크
                map[r][c] -= howmuch;
                map[rr][cc] += howmuch;
            }
        }
    }
    
    //공기청정시작(시뮬레이션,인덱스조심)
    //위부터
    int r1 = Air_row-1;
    for (int r = r1 - 2; r >= 0; r--) map[r + 1][0] = map[r][0]; //아래로
    for (int c = 1; c < C; c++) map[0][c - 1] = map[0][c]; //왼쪽으로
    for (int r = 1; r <= r1; r++) map[r - 1][C-1] = map[r][C-1]; //위로
    for (int c = C - 1; c > 0; c--) map[r1][c] = map[r1][c - 1]; //오른쪽으로
    map[r1][1] = 0;
    //아래
    int r2 = Air_row;
    for (int r = r2 + 2; r < R; r++) map[r - 1][0] = map[r][0]; //위로
    for (int c = 1; c < C; c++) map[R - 1][c - 1] = map[R - 1][c];//왼쪽으로 [R-1]
    for (int r = R - 2; r >= r2; r--) map[r + 1][C-1] = map[r][C-1];//아래로
    for (int c = C - 2; c > 0; c--) map[r2][c + 1] = map[r2][c]; //오른쪽으로
    map[r2][1] = 0;
    
}
 
int main()
{
    cin >> R >> C >> T; //row, col, time
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> map[i][j];
            if (map[i][j] == -1) { Air_row = i; } //공기청정기의 row정보를 저장
        }
    }
 
    for (int i = 0; i < T; i++) {
        diffusion();
    }
 
    Show();
    return 0;
}