[SWEA_모의SW역량테스트] 5653번 - 줄기세포 배양

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRJ8EKe48DFAUo

SW Expert Academy

삼성 SWEA의 모의 역량문제 5653번 '줄기세포 배양'문제다.

꽤 오랜시간 헤맸던 문제인데 그 이유는 지나치게 loop를 돌아 시간초과가 떴기 때문이다.

 

결과적으로 벡터에 새로 생겨나는 세포들의 정보를 저장해두고, 중복해서 생성될 시 vector를 순회해서 동일 위치에 생명력이 더 낮은 세포가 존재한다면 그것을 지우고 (vector.erase(vector.begin()+idx)) 새롭게 추가해주었더니 시간이 매우 단축되었다 !

 

기존 테스트케이스 5개의 실행속도가 약 0.5초 조금 넘었는데 이렇게 바꾸니 0.28초로 거의 반이나 줄어들었다.

특별히 조건이 까다롭진 않았지만 그래도 지도의 범위를 유추해서 풀게하는 문제의 유형은 처음부터 생각을 좀 하게 했다. 나같은 경우에는 비활성->활성을 고려해 300초가 지나더라도 한 방향으로 최대 150칸 이동할 수 있기 때문에, 상하또는 좌우로 150칸씩, M과 N의 최대값 50을 고려해 150 + 50 + 150 = 350의 크기를 선언했다.

 

아래는 소스코드 전체.

#include <iostream>
#include <vector>
#define maxlen 350
using namespace std;
typedef struct cell{
    bool isEmpty;
    bool isAlive;
    int aliveTime, refreshTime, HP;
}cell;
typedef struct dir{
    int dr, dc;
}dir;
dir direction[4] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
cell map[maxlen][maxlen];
int N, M, K, T;
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    for (int tc = 0; tc < T; tc++){
        cin >> N >> M >> K;
        cell a;
        a.isEmpty = true;
        a.isAlive = false;
        a.aliveTime = -1;
        a.refreshTime = -1;
        a.HP = -1;
        for (int i = 0; i < maxlen; i++){
            for (int j = 0; j < maxlen; j++){
                map[i][j] = a;
            }
        }        
        for (int i = 150; i < 150 + N; i++){
            for (int j = 150; j < 150 + M; j++){
                int hp;
                cin >> hp;
                if (hp == 0){
                    continue;
                }
                else{
                    map[i][j].HP = hp;
                    map[i][j].isAlive = true;
                    map[i][j].isEmpty = false;
                    map[i][j].refreshTime = hp;
                    map[i][j].aliveTime = hp;
                }
            }
        }
        int time = 0;
        vector<pair<int, pair<int, int> > > v;
 
        while (1){
            time++;
            for (int r = 0; r < maxlen; r++){
                for (int c = 0; c < maxlen; c++){
                    if (map[r][c].isAlive){
                        if (map[r][c].refreshTime > 0){
                            map[r][c].refreshTime--;
                            continue;
                            // 살아있고 비활성 상태라면
                        }
                        else if (map[r][c].refreshTime == 0 && map[r][c].aliveTime > 0){
                            map[r][c].aliveTime--;
                            if (map[r][c].aliveTime == 0) map[r][c].isAlive = false;
                            if (map[r][c - 1].isEmpty || map[r][c + 1].isEmpty || map[r + 1][c].isEmpty || map[r - 1][c].isEmpty){
                                // 살아있고 활성상태이며 주변에 퍼질 수 있으면
                                for (int next = 0; next < 4; next++){
                                    int nr = r + direction[next].dr;
                                    int nc = c + direction[next].dc;
                                    if (map[nr][nc].isEmpty && map[nr][nc].HP < map[r][c].HP){ // 다음이 비어있고, 현재 HP가 더 크면
                                        int erase_val = map[nr][nc].HP;
                                        map[nr][nc].HP = map[r][c].HP;
                                        v.push_back(make_pair(map[r][c].HP, make_pair(nr, nc)));
                                        for (int k = 0; k < v.size(); k++){
                                            if (v[k].second.first == nr && v[k].second.second == nc && v[k].first == erase_val){
                                                    v.erase(v.begin() + k);
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        
 
            // ADD 모두 갱신하고 map도 갱신함.
            // 이제 ADD에서 isAlive인 것들 모두 map에 반영.
            for (int vidx = 0; vidx < v.size(); vidx++){
                int r = v[vidx].second.first;
                int c = v[vidx].second.second;
                int val = v[vidx].first;
                cell a;
                a.aliveTime = val;
                a.HP = val;
                a.refreshTime = val;
                a.isAlive = true;
                a.isEmpty = false;
                map[r][c] = a;
            }
            v.clear();
            if (time == K){
                int sum = 0;
                for (int r = 0; r < maxlen; r++){
                    for (int c = 0; c < maxlen; c++){
                        if (map[r][c].isAlive) sum++;
                    }
                }
                cout << "#" << tc + 1 << " " << sum << '\n';
                break;
            }
        }
    }
    return 0;
}