Gidhub BE Developer

[SW Expert Academy] 5653. 줄기세포 배양

2018-10-16
goodGid

Problem

Problem URL : 줄기세포 배양


[1] Answer Code (18. 10. 16)

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#define p pair<int,int>
using namespace std;

// 동서남북
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int map[700][700];

int n,m,k;
int ans;

struct Node{
    int x;
    int y;
    int time;
    Node(int a, int b, int c): x(a),y(b),time(c){};
};


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int TC;
    cin >> TC;
    
    for(int tc=1; tc<=TC; tc++){
        memset(map,0,sizeof(map));
        ans = 0;
        cin >> n >> m >> k;
        
        /*
         생명령을 기준으로 처리할 것이기에
         큐를 11 사이즈로 잡는다.
         (1 ~ 10 까지의 생명력을 갖는다는 조건)
         */
        queue<Node> q[11];
        
        for(int i=350; i<n+350; i++){
            for(int j=350; j<m+350; j++){
                cin >> map[i][j];
                if(map[i][j])
                    /*
                     초기 상태에서 죽을 때까지
                     총 걸리는 시간은
                     [ 주어진 시간 * 2 ] 시간이다.
                     */
                    q[ map[i][j] ].push( Node(i, j, map[i][j]*2) );
            }
        }
        
        while (k--) {
            for(int i=10; i>=1; i--){
                int size = (int) q[i].size();
                /*
                 i = 8 일 때
                 8만큼의 생명력을 갖고 있는 줄기 세포만을 갖고 있는
                 큐에 대해서 작업을 할 것이다.
                 */
                for(int j=0; j<size; j++){
                    int x = q[i].front().x;
                    int y = q[i].front().y;
                    int time = q[i].front().time;
                    q[i].pop();
                    
                    time--;
                    /*
                     i = 8 일 때
                     map[x][y] = 8
                     time은 16에서 지속적으로 줄어든다.
                     이 때
                     map[x][y] > time이 된다면
                     즉 [ 비활성화 -> 활성 ] 상태가 되는
                     그 순간에만 번식을 하게 된다.
                     그 이후로는 map[nx][ny]값이 0이 아니기 때문에
                     실질적인 작업이 이뤄지지 않는다.
                     */
                    if(map[x][y] > time){
                        for(int k=0; k<4; k++){
                            int nx = x + dx[k];
                            int ny = y + dy[k];
                            if(map[nx][ny] == 0){
                                map[nx][ny] = map[x][y];
                                q[i].push( Node(nx,ny,map[nx][ny]*2) );
                            }
                        } // end of for k
                    } // end of if
                    
                    /*
                     i = 8 일 때
                     map[x][y] = 8로 고정이 되어 있고
                     time 값은 지속적으로 줄어든다.
                     이 때 8을 기준으로
                     8보다 크면 비활성화
                     8보다 작으면 활성화 상태이다.
                     그리고 time이 0이 된다면 죽은 상태가 된다.
                     그렇기 때문에 활성화 상태에서 죽기까지
                     해당 줄기 세포에 대해서는
                     지속적으로 생존 시간만 감소시켜야 한다.
                     그리고 time이 0이 된다면 죽은 상태가 되기 때문에
                     큐에 다시 push를 하지 않는다.
                     // 물론 활성화 상태에서 위 if문에 들어가지만
                     // map[nx][ny] 값이 0이 아니기 때문에
                     // 실질적인 작업은 이뤄지지 않는다.
                     // 즉 번식은 1번만 이뤄진다.
                     */
                    if(time > 0){
                        q[i].push(Node(x,y,time));
                    }
                } // end of for j
            } // end of for i
        } // end of while
        
        /*
         i값은 생명력을 뜻한다.
         q[i]에 남아있는 Node들은
         활성화 / 비활성화 상태 종류들 뿐이다.
         죽은 상태는 큐에 다시 push를 해주지 않았기 때문이다.
         */
        for(int i=1; i<11; i++)
            ans += q[i].size();
        
        cout << "#" << tc << " " << ans << endl;
    }

    return 0;
}

Review

  • 어려웠다.

  • 스스로 해결 못해서 답을 참고해서 풀었다.

  • 문제를 너무 어렵게 접근해서 해결하려고 했다.

  • 를 배열로 사용해서 문제를 풀다니… 혁신적이였다.

  • 맵 사이즈가 주어지지 않은 점이 신선했다.

  • 그래서 Max 맵의 사이즈를 계산해야했다.

  • 처음엔 50x50일 때 모든 생명력이 1이라고 가정한다면
    최대 300시간이기 때문에
    300 + 50 + 300으로 계산해서 넉넉잡아 700을 잡았다.

  • 그런데 생각해보니 생명력이 1일 때 1시간마다 번식하는게 아니라
    2시간마다 번식이 가능했다. 그렇기 때문에 150 + 50 + 150으로 잡아도 AC 할 수 있다.


Comments

Content