백준 10282번: 해킹 (C++)

접근

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

10282번: 해킹

전형적인 다익스트라 알고리즘 문제였다. 이번 문제에서는 우선순위 큐를 쓰지 않고 그냥 bfs 방식으로 풀었다.

감염된 지점부터 의존성이 있는 주변의 지점들을 방문하면서 해당하는 감염 시간을 저장해주고, 큐에 추가해준다. 그리고 다음 위치에서도 같은 작업을 해주되, 방문한 곳을 또 방문하게 된다면 (현재 위치 감염까지 걸린 시간 + 다음 위치 감염에 걸리는 시간) 과 (기존에 저장된 다음 위치 감염까지 걸린 시간) 을 비교하여 더 작은 것을 저장해주고, 그에 따라 큐에 추가할지 아닐지를 결정하여 탐색을 지속한다.

탐색을 완료한 후 visited 배열을 검사하여 거리가 INF 가 아닌 컴퓨터들의 갯수를 카운트하고, 또한 거리가 INF가 아닌 컴퓨터들의 감염 시간 중 가장 큰값을 찾아 출력해준다.

코드

#include <cstring>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

#define endl '\n'
#define MAX_N 10002
#define INF 10000001

int T, n, d, c, a, b, s, anum, atime;
int visited[MAX_N];
vector<pair<int, int>> dependency[MAX_N];

int MaxVal(int a, int b) {
    if (a >= b) {
        return a;
    } else {
        return b;
    }
}

void bfs() {
    for (int i = 1; i <= n; i++) {
        visited[i] = INF;
    }
    queue<int> Q;
    Q.push(c);
    visited[c] = 0;
    while (!Q.empty()) {
        int now = Q.front();
        Q.pop();
        for (int i = 0; i < dependency[now].size(); i++) {
            int next = dependency[now][i].first;
            int time = dependency[now][i].second;
            if (visited[now] + time < visited[next]) {
                Q.push(next);
                visited[next] = visited[now] + time;
            }
        }
    }
    anum = 0;
    atime = 0;
    for (int i = 1; i <= n; i++) {
        if (visited[i] < INF) {
            anum++;
            atime = MaxVal(atime, visited[i]);
        }
    }
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> T;
    for (int k = 0; k < T; k++) {
        cin >> n >> d >> c;
        for (int i = 0; i < d; i++) {
            cin >> a >> b >> s;
            dependency[b].push_back(make_pair(a, s));
        }
        bfs();
        cout << anum << ' ' << atime << endl;
        for (int i = 1; i <= n; i++) {
            dependency[i].clear();
        }
    }

    return 0;
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!