해결) 5653 줄기세포 배양

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
 
using namespace std;
 
// 변수
int height, width, total_time;
int flag[700][700];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };
int cen_x = 400, cen_y = 400;
 
// 비교 연산 클래스
class cmp {
public:
    bool operator()(pair<pair<int, int>, pair<int, int> > a, pair<pair<int, int>, pair<int, int> > b) {
        int tmp1 = a.second.second;
        int tmp2 = b.second.second;
 
        if (tmp1 < tmp2)
            return true;
        else
            return false;
    }
};
 
// 우선순위 큐
queue<pair<pair<int, int>, pair<int, int> > > pq;
// 우선순위 큐 2 - tmp_pq
priority_queue<pair<pair<int, int>, pair<int, int> >,
    vector<pair<pair<int, int>, pair<int, int> > >, cmp> tmp_pq;
 
// 함수 모음
void initialize();
void time_pass();
 
// 함수들
int main() {
    int test;
    scanf("%d", &test);
 
    for (int t = 1; t <= test; t++) {
        initialize();
 
        for (int i = 0; i < total_time; i++) 
            time_pass();
 
        printf("#%d %d\n", t, pq.size());    
    }
}
 
void time_pass() {
    while (!pq.empty()) {
        // 우선순위 큐 추출
        int y = pq.front().first.first;
        int x = pq.front().first.second;
        int t_cnt = pq.front().second.first;
        int power = pq.front().second.second;
 
        pq.pop();
 
        // t_cnt 증가
        t_cnt++;
 
        // 비활성화 -> 활성화 전환
        if (t_cnt == power) 
            tmp_pq.push(make_pair(make_pair(y, x), make_pair(t_cnt, power)));        
        // 활성화 전이
        else if ((t_cnt > power) && (t_cnt <= 2 * power)) {
            for (int i = 0; i < 4; i++) {
                int xx = x + dx[i];
                int yy = y + dy[i];
 
                if (flag[yy][xx] == 0)
                    tmp_pq.push(make_pair(make_pair(yy, xx), make_pair(0, power)));
            }
            if (t_cnt != 2 * power)
                tmp_pq.push(make_pair(make_pair(y, x), make_pair(t_cnt, power)));
            if (t_cnt == 2 * power)
                flag[y][x] = -power;                
        }
        // 비활성화 유지
        else if (t_cnt < power) 
            tmp_pq.push(make_pair(make_pair(y, x), make_pair(t_cnt, power)));        
    }
 
    while (!tmp_pq.empty()) {
        // 우선순위 큐 추출
        int y = tmp_pq.top().first.first;
        int x = tmp_pq.top().first.second;
        int t_cnt = tmp_pq.top().second.first;
        int power = tmp_pq.top().second.second;
 
        tmp_pq.pop();
 
        if (t_cnt == 0) {
            // 비어있는 셀일 경우, 전이
            if (flag[y][x] == 0) {
                flag[y][x] = power;        
                pq.push(make_pair(make_pair(y, x), make_pair(0, power)));
            }
        }
        else 
            pq.push(make_pair(make_pair(y, x), make_pair(t_cnt, power)));
        
    }
}
 
void initialize() {
    // queue empty
    while (!pq.empty())
        pq.pop();
    while (!tmp_pq.empty())
        tmp_pq.pop();
 
    // 변수
    scanf("%d %d %d", &height, &width, &total_time);
 
    // memset
    memset(flag, 0, sizeof(flag));
 
    // scanf 배열 입력
    int tmp;
    for (int i = cen_y; i < cen_y + height; i++) 
        for (int j = cen_x; j < cen_x + width; j++) {
            scanf("%d", &tmp);
 
            // 줄기세포가 있을 경우, flag 처리
            if (tmp > 0) {
                flag[i][j] = tmp;
                
                // 줄기세포에 관한 정보를 우선순위 큐에 대입
                pq.push(make_pair(make_pair(i, j), make_pair(0, tmp)));
            }
        }
    
}

드디어 풀었다..ㅠㅠ

역시 아무리 봐도 자료구조 자체에서는 문제가 없었다.

다만, 내가 우선순위 큐 안에 원소들을 좀 많이 넣다보니, 그 수의 몇제곱만큼의 연산량이 늘어버려서 

시간이 미세한 차이로 초과했던 것 같다.

이것도 거의 2일 잡아먹었다.

우선순위 큐를 활용해야 하는 문제 두 문제에서 고배를 마셨다

해당 유형을 잘 파헤쳐봐야겠다

더불어서, 시간 복잡도에 대한 염두도 꼭 하면서 코딩해야겠다

# 시간 복잡도 줄이기 위한 연산 

1. 우선순위 큐의 비교 연산자를 하나 빼줬다 - cmp 함수

2. 두 개의 우선순위 큐를 갖고 있었는데, 우선순위 큐 중에서 하나를 아예 빼줬다 (일반 큐로 전환)

- 우선순위 큐의 경우, 원소를 넣자마자 순서 배치를 하기 때문에, 

  자연스럽게 시간복잡도가 NlogN 으로 계산된다.

- 따라서, 굳이 "우선순위" 큐가 필요하지 않는 이상, 일반 큐를 사용해주자

3. 가장 중요했던 것, 큐에 원서를 집어넣을때도 선별해서 집어넣자(꼭)

   안그러면 몇 제곱 배의 연산량만큼 늘어나기 때문에, 치명적이다