네트워크 복구

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

문제

N(1 ≤ N ≤ 1,000)개의 컴퓨터로 구성된 네트워크가 있다.

이들 중 몇 개의 컴퓨터들은 서로 네트워크 연결이 되어 있어 서로 다른 두 컴퓨터 간 통신이 가능하도록 되어 있다.

통신을 할 때에는 서로 직접 연결되어 있는 회선을 이용할 수도 있으며, 회선과 다른 컴퓨터를 거쳐서 통신을 할 수도 있다.

각 컴퓨터들과 회선은 그 성능이 차이가 날 수 있다.

따라서 각각의 직접 연결되어 있는 회선을 이용해서 통신을 하는데 걸리는 시간이 서로 다를 수 있다.

심지어는 직접 연결되어 있는 회선이 오히려 더 느려서, 다른 컴퓨터를 통해서 통신을 하는 것이 더 유리할 수도 있다.

직접 연결되어 있는 회선을 사용할 경우에는 그 회선을 이용해서 통신을 하는 데 드는 시간만큼이 들게 된다.

여러 개의 회선을 거치는 경우에는 각 회선을 이용해서 통신을 하는 데 드는 시간의 합만큼의 시간이 걸리게 된다.

어느 날, 해커가 네트워크에 침입하였다.

네트워크의 관리자는 우선 모든 회선과 컴퓨터를 차단한 후, 해커의 공격을 막을 수 있었다.

관리자는 컴퓨터에 보안 시스템을 설치하려 하였는데, 버전 문제로 보안 시스템을 한 대의 슈퍼컴퓨터에만 설치할 수 있었다.

한 컴퓨터가 공격을 받게 되면, 네트워크를 통해 슈퍼컴퓨터에 이 사실이 전달이 되고,

그러면 슈퍼컴퓨터에서는 네트워크를 이용해서 보안 패킷을 전송하는 방식을 사용하기로 하였다.

준비를 마친 뒤, 관리자는 다시 네트워크를 복구하기로 하였다. 이때, 다음의 조건들이 만족되어야 한다.

1. 해커가 다시 공격을 할 우려가 있기 때문에, 최소 개수의 회선만을 복구해야 한다.

물론, 그렇다면 아무 회선도 복구하지 않으면 되겠지만, 이럴 경우 네트워크의 사용에 지장이 생기게 된다.

따라서 네트워크를 복구한 후에 서로 다른 두 컴퓨터 간에 통신이 가능하도록 복구해야 한다.

2. 네트워크를 복구해서 통신이 가능하도록 만드는 것도 중요하지만,

해커에게 공격을 받았을 때 보안 패킷을 전송하는 데 걸리는 시간도 중요한 문제가 된다.

따라서 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이,

원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다.

원래의 네트워크에 대한 정보가 주어졌을 때,

위의 조건을 만족하면서 네트워크를 복구하는 방법을 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 N, M이 주어진다.

다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다.

이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다는 의미이다.

컴퓨터들의 번호는 1부터 N까지의 정수이며, 1번 컴퓨터는 보안 시스템을 설치할 슈퍼컴퓨터이다.

모든 통신은 완전쌍방향 방식으로 이루어지기 때문에,

한 회선으로 연결된 두 컴퓨터는 어느 방향으로도 통신할 수 있다.

출력

첫째 줄에 복구할 회선의 개수 K를 출력한다.

다음 K개의 줄에는 복구한 회선을 나타내는 두 정수 A, B를 출력한다.

이는 A번 컴퓨터와 B번 컴퓨터를 연결하던 회선을 복구한다는 의미이다.

출력은 임의의 순서대로 하며, 답이 여러 개 존재하는 경우에는 아무 것이나 하나만 출력하면 된다.

예제 입력 1

4 5
1 2 1
1 4 4
1 3 2
4 2 2
4 3 3

예제 출력 1

3
1 2
3 1
4 2

https://www.acmicpc.net/board/view/70830 <- 참조

예제 입력 A

6 12
5 6 4 
4 3 3 
6 5 8 
5 1 4 
1 6 3 
6 2 6 
1 2 4 
3 2 8 
4 2 5 
5 3 5 
1 4 2 
2 4 8

예제 출력 A

5
2 1
3 4
4 1
5 1
6 1

예제 입력 B

8 14
2 4 1 
7 6 7 
1 5 7 
1 4 6 
5 3 9 
4 1 5 
7 8 3 
6 1 4 
4 2 3 
5 6 3 
7 5 9 
7 1 9 
2 1 1 
7 4 6

예제 출력 B

7
2 1
3 5
4 2
5 1
6 1
7 4
8 7

예제 입력 C

24 45
20 16 5 
24 7 9 
24 18 6 
4 2 7 
23 5 7 
8 19 5 
1 6 3 
9 8 7 
2 3 5 
11 12 4 
4 20 1 
2 16 5 
22 11 1 
17 10 4 
3 7 4 
18 10 9 
21 2 5 
20 18 3 
5 10 5 
15 2 4 
14 10 7 
4 15 9 
20 10 8 
14 12 8 
12 8 1 
23 14 8 
15 24 9 
12 5 1 
15 8 3 
21 15 7 
12 7 6 
18 12 5 
13 7 2 
7 10 3 
24 5 1 
15 10 7 
3 2 2 
22 5 6 
3 16 4 
1 12 1 
9 17 3 
17 12 7 
8 12 8 
11 15 7 
4 9 5

예제 출력 C

23
2 15
3 7
4 20
5 12
6 1
7 12
8 12
9 8
10 5
11 12
12 1
13 7
14 12
15 8
16 20
17 12
18 12
19 8
20 18
21 15
22 11
23 5
24 5

출처

• 빠진 조건을 찾은 사람: his130
• 어색한 표현을 찾은 사람: mwy3055

알고리즘 분류

• 그래프 이론
• 데이크스트라

풀이 과정

통과된 코드

map을 사용하는 생각이 바로 떠올라서 빠르게 해결

#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;

// N(1 ≤ N ≤ 1,000)개의 컴퓨터
constexpr int MAXN = 1001;
constexpr int INF = INT32_MAX;

///*
//각 노드에 연결되어 있는 노드에 대한 정보를 담는 벡터
//a번 노드에서 b번 노드로 가는 비용이 c라는 의미
//graph[a].push_back((make_pair(B, C));
//*/
vector<pair<int, int>> graph[MAXN];

// Dijkstra 알고리즘에 사용할 우선순위 큐
priority_queue<pair<int, int>> myPQ;

// 문제의 결과를 출력하기 위한 map 
map<int, int> myMap;

// dist[i][j]  
// => i 에서 j 까지의 최단거리 (임시 노드)
int timeArr[MAXN];

// dist[i][j]  
// => i 에서 j 까지의 최단거리 (임시 노드)
int cntArr[MAXN];

// N : 정점의 개수, M : 간선의 개수
// U: 현재 노드, V : 이웃 노드, t : 통신 시간
int N, M, U, V, t;


void Dijkstra(int start)
{
    // 임시배열 초기화
    for (int i = 1; i <= N; i++) timeArr[i] = INF;
    // 우선순위 큐에 삽입.
    myPQ.push({ 0, start }); // < first : 거리 , second : 노드 인덱스 >
    timeArr[start] = 0;

    while (!myPQ.empty()) {
        // -를 붙이는 이유는 우선순위 큐를 이용하여 정렬하기 위함이다.
        // (최소힙으로 구현)
        int nCost = -myPQ.top().first;
        int now = myPQ.top().second;
        myPQ.pop();

        // 이미 담겨 있는 것보다 거리가 크면 넘어간다.
        if (timeArr[now] < nCost) continue;

        // 해당 노드에서 연결된 모든 경로를 확인
        for (int i = 0; i < graph[now].size(); i++) {
            // 0이라면 길이 없다는 의미 continue
            if (graph[now][i].second == 0) continue;
            // disSum = 임시 노드 + 현재 노드에서 i로가는 비용
            int disSum = nCost + graph[now][i].second;
            // 비용이 더 작다면 최단경로 테이블 값을 갱신.
            if (disSum < timeArr[graph[now][i].first]) {
                // 임시 노드 업데이트
                timeArr[graph[now][i].first] = disSum;
                // 우선순위 큐에 (거리, 노드 인덱스) 푸시
                myPQ.push(make_pair(-disSum, graph[now][i].first));

                // 만약 map의 key 값이 겹친다면 해당 값을 지운다.
                if (myMap.count(graph[now][i].first)) myMap.erase(graph[now][i].first);
                // 도착지를 Key 값으로 map에 저장
                myMap.insert(make_pair(graph[now][i].first, now));
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
    // cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;

    for (int i = 0; i < M; i++) {
        cin >> U >> V >> t;
        // 양방향 통신 가능
        graph[U].push_back(make_pair(V, t));
        graph[V].push_back(make_pair(U, t)); 
    }

    Dijkstra(1);

    // map의 사이즈를 출력합니다.
    cout << myMap.size() << "\n";

    // 복구한 회선을 출력
    for (auto it = myMap.begin(); it != myMap.end(); it++) 
        cout << it->first << " " << it->second << "\n";

	return 0;
}