[BOJ 10282] 해킹

10282번: 해킹

 

1. 문제 설명

 

2. 구현 아이디어 - 메모리 초과

문제 설명에 있는 예제 입력에 그린 것처럼 컴퓨터끼리의 관계를 그래프로 표현할 수 있고, 여기서 s초를 간선의 값이라고 생각하면 최초로 해킹 당한 컴퓨터부터 다른 컴퓨터까지의 최단 경로를 탐색하는 문제라고 생각할 수 있다.

 

한 노드에 대해서만 최단 경로를 생각하면 되기 때문에 다익스트라 알고리즘을 사용해보자.

 

다익스트라 알고리즘의 개념에 대해서는 아래 포스트에 정리해두었다.

최단거리 알고리즘 - 다익스트라 & 플로이드 워셜

 

#include <bits/stdc++.h>

using namespace std;

#define INF 987654321

int t; // 테스트 케이스의 개수
int n, d, c; // 컴퓨터 개수, 의존성 개수, 해킹당한 컴퓨터의 번호
int a, b, s; // a가 b를 의존하며, b가 감염되면 s초 후 a도 감염된다
int dist, now, cost; // 다익스트라 알고리즘을 구현하며 사용할 변수

void dijkstra(vector<vector<int>> &arr, vector<int> &distance, int start) {
    // 우선순위 큐를 활용
    // 작은 값이 우선이 되도록 greater를 사용
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

    // 시작 노드 삽입
    pq.push({0, start}); // 거리, 노드 순
    // 시작 노드에 대한 최단거리는 0으로 초기화
    distance[c] = 0;

    while (!pq.empty()) {
        dist = pq.top().first;
        now = pq.top().second;
        pq.pop();

        // 이미 방문한 노드라면 skip
        if (dist < distance[now]) continue;
        for (int i = 1; i <= n; ++i) {
            // 의존 관계가 없거나 자기 자신인 경우 skip
            if (arr[now][i] == INF || i == start) continue;
            // 새로운 최단 거리 cost를 계산하고 현재 최단 거리보다 짧다면 갱신
            cost = dist + arr[now][i];
            if (cost < distance[i]) {
                pq.push({cost, i});
                distance[i] = cost;
            }
        }
    }
}

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

    cin >> t;
    while (t--) {
        cin >> n >> d >> c;

        // 노드 간의 거리를 저장하는 인접 행렬
        vector<vector<int>> arr(n+1, vector<int>(n+1, INF));
        // 최단 거리를 저장
        vector<int> distance(n+1, INF);
        for (int i = 1; i <= n; ++i) {
            arr[i][i] = 0;
        }

        // 의존 정보 입력 받음
        while (d--) {
            cin >> a >> b >> s;
            arr[b][a] = s;
        }

        // 다익스트라 알고리즘을 사용하여 최단 거리 계산
        dijkstra(arr, distance, c);

        int cnt = 0;
        int ret = 0;
        // 총 감염되는 컴퓨터 수와 마지막 컴퓨터가 감염되기까지 걸리는 시간 계산
        for (int i = 1; i <= n; ++i) {
            if (distance[i] != INF) {
                cnt++;
                if (distance[i] > ret) ret = distance[i];
            }
        }

        cout << cnt << " " << ret << "\n";
    }

    return 0;
}

 

25%쯤에서 메모리 초과가 떴다 :(

 

3. 구현 아이디어 2 - 맞았습니다!!

노드 간 거리를 저장할 때 인접 행렬을 사용하고, 처음에는 모두 INF로 초기화해주기 때문에 해당 부분에서 메모리 초과가 발생했다고 생각했다.

 

인접 행렬 대신 인접 리스트 방식을 사용하도록 코드를 수정해서 문제를 해결할 수 있었다.

// 1. 다익스트라 알고리즘에서 거리 정보를 사용하는 부분 수정
void dijkstra(map<int, vector<pair<int, int>>> &mp, vector<int> &distance, int start) {
    // 중략 ..
    while (!pq.empty()) {
        // 중략 ..
        for (auto elem : mp[now]) {
            cost = dist + elem.second;
            if (cost < distance[elem.first]) {
                pq.push({cost, elem.first});
                distance[elem.first] = cost;
            }
        }
    }
}

int main() {
    // 중략 ..
    
    // 2. 의존 정보를 입력 받는 부분 수정
    map<int, vector<pair<int, int>>> mp;

    while (d--) {
        cin >> a >> b >> s;
        mp[b].push_back({a, s}); // 노드, 간선
    }
    
    // 중략 ..
}