[백준]백준 18405번(C++)

https://www.acmicpc.net/problem/18405

18405번: 경쟁적 전염

 

문제 해결 과정

 

• 바이러스는 숫자가 작은 바이러스부터 전염이 되어야 한다. 따라서 우선순위 큐를 이용하여 큐에 바이러스를 저장할 때마다 그 바이러스의 우선순위가 높으면 자동으로 앞으로 오게 한다.
• 1초가 지날 때마다 바이러스가 전염되게 하고, 1초가 종료되면 새롭게 전염된 바이러스의 종류와 위치를 큐에 다시 저장한다. -> 이때 전염되는 과정에서 임시 큐에 새롭게 전염된 바이러스를 저장, 1초가 완전히 종료되면 기존 큐에 임시 큐의 내용을 다시 저장하는 방식을 채택함.

 

오류 해결 과정 (이 한 문제에서 백준에서 볼 수 있는 대표 결과 4개를 다 보았다)

결과화면...

1. 틀렸습니다 -> 시간초과: 우선순위 큐에 저장하는 것까지는 잘했는데, 우선순위큐는 자동으로 내림차순으로 정렬되기 때문에 오름차순 조건을 인자로 넣어주거나, 우선순위 앞에 마이너스를 넣어서 저장해야 오름차순으로 저장이 됨. 하지만 시간초과 발생
2. 시간 초과 -> 런타임 에러: 임시 바이러스 저장공간(이때는 벡터였음)에 바이러스를 저장해두고 초기화를 안시켜서 시간이 지날 때마다 엄청난 양의 데이터가 저장되고 있었음.. 난 그것도 모르고 기존 큐에 계속 삽입하니 그걸 전부 전염시키고 조건 확인하느라 시간초과 발생. 그래서 삭제를 진행했지만 런타임에러 발생
3. 런타임에러 -> 맞았습니다: 벡터의 앞부분을 삭제하기도 해보고 인덱스로 삭제해보기도 하고 iterator로 순회하면서 삭제해보기도 했는데 계속 에러 발생.. 알아보니 iterator가 순회를 할 때마다 주소값이 바뀌기 때문이라고 한다 (해결책은 여기) 그래서 임시 바이러스 저장공간을 그냥 큐로 선언하고 pop 해줬다. 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;

int N, K; //맵 크기, 바이러스 종류
int** virusMap; //전염될 맵
priority_queue<tuple<int, int, int>> vq;
priority_queue<tuple<int, int, int>> tmp_v;
int S, X, Y; //전염 시간, 위치 좌표

int dir[4][2] = {
    {1,0}, //상
    {0,1}, //우
    {-1, 0}, //하
    {0,-1} //좌
};

void input() {
    scanf("%d %d", &N, &K);
    
    //맵 메모리 할당
    virusMap = new int* [N + 1];
    for (int i = 0; i < N + 1; i++) virusMap[i] = new int[N + 1];

    //맵 정보 입력
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            int n = 0;
            scanf("%d", &n);
            virusMap[i][j] = n;
            if (n != 0) vq.push(make_tuple(n*-1, i, j)); //바이러스라면 큐에 삽입
        }
    }
    
    scanf("%d %d %d", &S, &X, &Y);
}

//전염시키기
void infect(int k, int x, int y) {
    for (int i = 0; i < 4; i++) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];

        if (nx >= 1 && nx <= N && ny >= 1 && ny <= N) {
            if (virusMap[nx][ny] == 0) {
                virusMap[nx][ny] = k; //해당 위치에 바이러스가 없어야만 전염 됨
                tmp_v.push(make_tuple(k*-1, nx, ny)); //새로운 자리를 추가
            }
        }
    }
}

void solution() {
    //전파시간 동안 실행
    for (int i = 0; i < S; i++) {
        while (!vq.empty()) {
            int k = get<0>(vq.top());
            int x = get<1>(vq.top());
            int y = get<2>(vq.top());
            vq.pop(); //삭제
            infect(k*-1, x, y);
        }
        
        while (!tmp_v.empty()) {
            vq.push(tmp_v.top());
            tmp_v.pop();
        }
    }
}

int main() {
    input();
    solution();
    printf("%d", virusMap[X][Y]);
}