2382 미생물 격리

#include <stdio.h>
#include <queue>
#include <vector>
#include <string.h>
 
using namespace std;
 
int width, total_time, num_micro;
int sum_bug[105][105];
 
// 비교 연산자 - pq 용 
class cmp {
public:
    bool operator()(pair<pair<int, int>, pair<int, int> > a, pair<pair<int, int>, pair<int, int> > b) {
        if (a.second.first > b.second.first)
            return true;
        else
            return false;
    }
};
 
// 비교연산자 - tmp_pq 용 
class cmp2 {
public:
    bool operator()(pair<pair<int, int>, pair<int, int> > a, pair<pair<int, int>, pair<int, int> > b) {
        if (a.second.first < b.second.first)
            return true;
        else
            return false;
    }
};
 
priority_queue<pair<pair<int,int>, pair<int,int> >, 
    vector<pair<pair<int, int>, pair<int, int> > >, cmp > pq;    // (y,x),(num_bug,dir)
priority_queue<pair<pair<int, int>, pair<int, int> >,
    vector<pair<pair<int, int>, pair<int, int> > >, cmp2 > tmp_pq;    // (y,x),(num_bug,dir)
 
// 함수들
void initialize();
void time_after();
 
void print_total(int time) {
    int rst_bug = 0;
    while (!pq.empty()) {
        int y = pq.top().first.first;
        int x = pq.top().first.second;
 
        rst_bug += sum_bug[y][x];
        pq.pop();
    }
 
    printf("#%d %d\n", time, rst_bug);
}
 
int main() {
    int test;
    scanf("%d", &test);
 
    for (int t = 1; t <= test; t++) {
        initialize();
 
        for (int i = 0; i < total_time; i++) 
            time_after();
        
        print_total(t);
    }
}
 
 
void time_after() {
    while (!tmp_pq.empty())
        tmp_pq.pop();
 
    while (!pq.empty()) {
        // 맨 위의 원소 확인 - 추출
        int y = pq.top().first.first;
        int x = pq.top().first.second;
        int num_bug = sum_bug[y][x];
        int cur_dir = pq.top().second.second;
 
        pq.pop();
 
        // sum_bug 초기화
        sum_bug[y][x] = 0;
 
        // 방향 확인 후 이동
        int next_x = x, next_y = y;
        if (cur_dir == 1)    next_y -= 1;
        if (cur_dir == 2)    next_y += 1;
        if (cur_dir == 3)    next_x -= 1;
        if (cur_dir == 4)    next_x += 1;
 
        // 경계선일 경우
        if (next_x == 0 || next_x == width - 1 || next_y == 0 || next_y == width - 1) {
            // 절반으로 벌레가 줄어들며
            num_bug /= 2;
 
            // 방향이 반대로 된다
            if (cur_dir == 1)    cur_dir = 2;
            else if (cur_dir == 2)    cur_dir = 1;
            else if (cur_dir == 3)    cur_dir = 4;
            else if (cur_dir == 4)    cur_dir = 3;
        }
        
        // tmp_pq 에 집어넣기
        if(num_bug > 0)            
            tmp_pq.push(make_pair(make_pair(next_y, next_x), make_pair(num_bug, cur_dir)));
    }
 
    // flag 배열 생성 - 겹치게 되는 경우 방지
    int flag[105][105] = { 0 };
 
    // tmp_pq 를 pq 에 집어넣기 + sum_bug 초기화
    while (!tmp_pq.empty()) {
        // 맨 위의 원소 확인 - 추출
        int y = tmp_pq.top().first.first;
        int x = tmp_pq.top().first.second;
        int num_bug = tmp_pq.top().second.first;
        int cur_dir = tmp_pq.top().second.second;
        tmp_pq.pop();
 
 
        // sum_bug 초기화
        sum_bug[y][x] += num_bug;
 
        // flag 확인하기 - 비어있을 경우에만 다음 큐로 넘긴다
        if (flag[y][x] == 0) {
            // pq 에 집어넣기
            pq.push(make_pair(make_pair(y, x), make_pair(num_bug, cur_dir)));
 
            flag[y][x] = 1;
        }
    }    
}
 
void initialize() {
    // memset
    memset(sum_bug, 0, sizeof(sum_bug));
 
    // scanf
    scanf("%d %d %d", &width, &total_time, &num_micro);
 
    // pq clear
    while (!pq.empty())
        pq.pop();
 
    // micro 각각
    for (int i = 1; i <= num_micro; i++) {
        int y, x, num_bug, cur_dir;
        scanf("%d %d %d %d", &y, &x, &num_bug, &cur_dir);
 
        pq.push(make_pair(make_pair(y, x), make_pair(num_bug, cur_dir)));
        sum_bug[y][x] = num_bug;
    }
}

어후...

이틀이나 걸렸다

물론 이틀 내내 한건 아니지만..

정신적으로 좀 힘들었다

푸는데만 6시간 걸린거같은데..

두 개의 우선순위 큐를 활용해서 풀어내는 문제였다

앞으로 시간 초과가 염려될 때는, 

초장부터 배열이 아닌 큐나 다른 효율적인 자료구조를 사용해야겠다

웬지 앞에서도 시간초과로 못 풀었던 문제도 우선순위 큐로 해결 가능할거같다..

힘들다..