문제

해법

이 문제는 제한 조건이 있는 BFS를 사용해야 합니다. 유성이 실시간으로 발생하기 때문에 이를 고려해야 합니다.

두 가지 접근 방법을 소개합니다:

해법 1

이것은 처음 시도했던 방법입니다.

유성을 실시간으로 처리하며, BFS는 시간 순서대로 탐색하므로 유성을 그때그때 생성할 수 있습니다. 유성이 발생하는 시간을 주의해야 합니다. 만약 t초에 유성이 발생하면, 그 초에는 이동할 수 없으므로 매 초마다 유성을 먼저 생성해야 합니다.

어떻게 특정 위치가 안전한지 판단할까요? 두 개의 배열을 사용하여 하나는 실시간 유성을 저장하고 다른 하나는 유성이 발생했는지를 저장합니다. 자세한 내용은 코드를 참조하세요.

구현 시 Bessie가 300을 넘어갈 수 있다는 점도 주의해야 합니다. 300은 단지 유성의 경계일 뿐입니다.

코드 1:

#include <iostream>
#include <queue>
#include <cstring>
#define MAX 401
using namespace std;

int m;
int danger[MAX][MAX];
int meteor[MAX][MAX];
bool visited[MAX][MAX];
int dirX[] = {0, 0, 1, -1};
int dirY[] = {1, -1, 0, 0};

struct Meteor {
    int x, y, time;
} meteors[500000];

bool isValid(int x, int y) {
    return x >= 0 && x <= 400 && y >= 0 && y <= 400;
}

void generateMeteors(int currentTime) {
    for (int i = 1; i <= m; i++) {
        if (meteors[i].time == currentTime) {
            meteor[meteors[i].x][meteors[i].y] = 1;
            for (int j = 0; j < 4; j++) {
                int nx = meteors[i].x + dirX[j];
                int ny = meteors[i].y + dirY[j];
                if (isValid(nx, ny)) meteor[nx][ny] = 1;
            }
        }
    }
}

void bfs() {
    queue<pair<int, pair<int, int>>> q;
    q.push({0, {0, 0}});
    visited[0][0] = true;
    
    while (!q.empty()) {
        auto current = q.front();
        q.pop();
        int currentTime = current.first;
        int cx = current.second.first;
        int cy = current.second.second;
        
        generateMeteors(currentTime);
        
        if (!danger[cx][cy]) {
            cout << currentTime << endl;
            return;
        }
        
        for (int i = 0; i < 4; i++) {
            int nx = cx + dirX[i];
            int ny = cy + dirY[i];
            if (isValid(nx, ny) && !meteor[nx][ny] && !visited[nx][ny]) {
                visited[nx][ny] = true;
                q.push({currentTime + 1, {nx, ny}});
            }
        }
    }
}

int main() {
    memset(visited, false, sizeof(visited));
    memset(meteor, 0, sizeof(meteor));
    
    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> meteors[i].x >> meteors[i].y >> meteors[i].time;
        danger[meteors[i].x][meteors[i].y] = 1;
        for (int j = 0; j < 4; j++) {
            int nx = meteors[i].x + dirX[j];
            int ny = meteors[i].y + dirY[j];
            if (isValid(nx, ny)) danger[nx][ny] = 1;
        }
    }
    generateMeteors(0);
    bfs();
    return 0;
}

해법 2

코치가 제공한 아이디어로, 첫 번째 해법보다 간결합니다.

각 지점이 유성에 의해 파괴되는 시간을 기록하는 배열을 만들어 사전 처리한 후 일반적인 BFS를 수행합니다.

사전 처리 중 해당 지점이 더 일찍 유성에 의해 파괴되면 기존 값으로 덮어씁니다.

0초에 유성이 있을 수 있으므로 안전한 지점을 0으로 표시하지 않아야 합니다.

첫 번째 해법에 비해 유성 시간과 유성이 발생했는지 여부를 한 배열로 처리할 수 있어 매우 간결합니다.

코드 2:

#include <iostream>
#include <queue>
#include <cstring>
#define MAX 401
using namespace std;

typedef pair<int, int> Point;
int m;
int destroyTime[MAX][MAX];
int visit[MAX][MAX];
int dirX[] = {0, 0, 1, -1};
int dirY[] = {1, -1, 0, 0};

struct Meteor {
    int x, y, time;
} meteors[500000];

bool isValid(int x, int y) {
    return x >= 0 && x <= 400 && y >= 0 && y <= 400;
}

void bfs() {
    queue<Point> q;
    q.push({0, 0});
    visit[0][0] = 0;
    
    while (!q.empty()) {
        Point current = q.front();
        q.pop();
        
        if (destroyTime[current.first][current.second] == -1) {
            cout << visit[current.first][current.second] << endl;
            return;
        }
        
        for (int i = 0; i < 4; i++) {
            int nx = current.first + dirX[i];
            int ny = current.second + dirY[i];
            if (isValid(nx, ny) && visit[nx][ny] == 0x3f3f3f3f && 
                (visit[current.first][current.second] + 1 < destroyTime[nx][ny] || destroyTime[nx][ny] == -1)) {
                visit[nx][ny] = visit[current.first][current.second] + 1;
                q.push({nx, ny});
            }
        }
    }
}

int main() {
    memset(destroyTime, -1, sizeof(destroyTime));
    memset(visit, 0x3f3f3f3f, sizeof(visit));
    
    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> meteors[i].x >> meteors[i].y >> meteors[i].time;
    }
    
    for (int i = 1; i <= m; i++) {
        if (destroyTime[meteors[i].x][meteors[i].y] == -1 || meteors[i].time < destroyTime[meteors[i].x][meteors[i].y])
            destroyTime[meteors[i].x][meteors[i].y] = meteors[i].time;
        for (int j = 0; j < 4; j++) {
            int nx = meteors[i].x + dirX[j];
            int ny = meteors[i].y + dirY[j];
            if (isValid(nx, ny) && (destroyTime[nx][ny] == -1 || meteors[i].time < destroyTime[nx][ny]))
                destroyTime[nx][ny] = meteors[i].time;
        }
    }
    
    bfs();
    return 0;
}