BOJ 2211 네트워크 복구
N(1 ≤ N ≤ 1,000)개의 컴퓨터로 구성된 네트워크가 있다. 이들 중 몇 개의 컴퓨터들은 서로 네트워크 연결이 되어 있어 서로 다른 두 컴퓨터 간 통신이 가능하도록 되어 있다. 통신을 할 때에는 서로 직접 연결되어 있는 회선을 이용할 수도 있으며, 회선과 다른 컴퓨터를 거쳐서 통신을 할 수도 있다.
각 컴퓨터들과 회선은 그 성능이 차이가 날 수 있다. 따라서 각각의 직접 연결되어 있는 회선을 이용해서 통신을 하는데 걸리는 시간이 서로 다를 수 있다. 심지어는 직접 연결되어 있는 회선이 오히려 더 느려서, 다른 컴퓨터를 통해서 통신을 하는 것이 더 유리할 수도 있다. 직접 연결되어 있는 회선을 사용할 경우에는 그 회선을 이용해서 통신을 하는 데 드는 시간만큼이 들게 된다. 여러 개의 회선을 거치는 경우에는 각 회선을 이용해서 통신을 하는 데 드는 시간의 합만큼의 시간이 걸리게 된다.
어느 날, 해커가 네트워크에 침입하였다. 네트워크의 관리자는 우선 모든 회선과 컴퓨터를 차단한 후, 해커의 공격을 막을 수 있었다. 관리자는 컴퓨터에 보안 시스템을 설치하려 하였는데, 버전 문제로 보안 시스템을 한 대의 슈퍼컴퓨터에만 설치할 수 있었다. 한 컴퓨터가 공격을 받게 되면, 네트워크를 통해 슈퍼컴퓨터에 이 사실이 전달이 되고, 그러면 슈퍼컴퓨터에서는 네트워크를 이용해서 보안 패킷을 전송하는 방식을 사용하기로 하였다. 준비를 마친 뒤, 관리자는 다시 네트워크를 복구하기로 하였다. 이때, 다음의 조건들이 만족되어야 한다.
해커가 다시 공격을 할 우려가 있기 때문에, 최소 개수의 회선만을 복구해야 한다. 물론, 그렇다면 아무 회선도 복구하지 않으면 되겠지만, 이럴 경우 네트워크의 사용에 지장이 생기게 된다. 따라서 네트워크를 복구한 후에 서로 다른 두 컴퓨터 간에 통신이 가능하도록 복구해야 한다.
네트워크를 복구해서 통신이 가능하도록 만드는 것도 중요하지만, 해커에게 공격을 받았을 때 보안 패킷을 전송하는 데 걸리는 시간도 중요한 문제가 된다. 따라서 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다.
원래의 네트워크에 대한 정보가 주어졌을 때, 위의 조건을 만족하면서 네트워크를 복구하는 방법을 알아내는 프로그램을 작성하시오.
문제가 상당히 길다. 읽기 싫다.
간략히 요약하자면 1번 노드에 슈퍼컴퓨터를 설치하여 바이러스로 부터 컴퓨터를 보호할 것인데, 각 노드에 설치될 컴퓨터와 슈퍼컴퓨터 사이의 거리가 최소가 되도록 네트워크를 복구하라는 의미이다.
고치러 가보자.
문제 풀이
해결방법을 다익스트라로 접근하면 비교적 간단한 문제였다.
문제는 내가 한동안 최소 스패닝 트리로 접근했다는 점이다.
흑흑
얼핏 비슷한 듯 다른 두 알고리즘의 차이는 다음의 삽질기록에서 찾아볼 수 있다.
정리하고 나니까 생각보다 명확했다.
본격적으로 문제 풀이를 진행해보자.
가장 큰 핵심은 슈퍼컴퓨터와 다른 컴퓨터들 사이의 거리가 최소가 되도록 네트워크를 복구하라는 점이다.
즉, 두 접점사이의 최소거리를 파악하면 되니 다익스트라 알고리즘을 채택할 수 있을 것이다. 나 또한 다익스트라를 이용했다.
한가지 유의할 점은 출력의 형식이다.
첫째 줄에 복구할 회선의 개수 K를 출력한다. 다음 K개의 줄에는 복구한 회선을 나타내는 두 정수 A, B를 출력한다. 이는 A번 컴퓨터와 B번 컴퓨터를 연결하던 회선을 복구한다는 의미이다. 출력은 임의의 순서대로 하며, 답이 여러 개 존재하는 경우에는 아무 것이나 하나만 출력하면 된다.
흔하디 흔한 다익스트라 문제들과 달리 복구할 회선의 개수와 그 회선으로 연결된 두 컴퓨터를 출력하라고 한다.
여기서 약간의 고민이 필요한데 나는 다음과 같은 조건에 주목했다.
- 각 컴퓨터에 도달하는 회선은 유일하다.
말이 어려운데, 다익스트라는 두 접점사이의 최소거리를 파악하는 알고리즘이다.
즉, 각 접점의 최소거리를 갖는 간선은 오직 하나일 것이란 소리이다.
다음의 그래프가 있다고 생각해보자.
위의 문제의 예시로 나오는 그래프이기도 하다.
여기서 다익스트라 알고리즘을 진행한 후 채택되는 간선들은 무엇일까?
위의 3개의 간선이 채택될 것이다.
이러한 간선들 기억하기 위해 나는 해당 정점의 최소거리를 갖는 간선 은 유일하다는 점을 이용할 것이다.
그림으로 표현하자면 위와 같다.
결국은 최소거리가 갱신 될 때 마다, 그때 채택된 간선을 최소거리가 갱신된 정점을 기준으로 기억을 하는 것이다.
여기서 나는 자료구조 map을 선택했다.
갱신된 정점 번호를 Key로 갖고, 간선과 이어진 노드를 Value로 갖는 것이다.
map에서는 중복이 허용되지 않기에 유일한 값만을 가질 것이다.
코드
// BOJ 2211
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#define MAX 987'654'321
using namespace std;
using pii = pair<int, int>;
int N, M;
int DIST[1'001];
map<int, pii> m;
vector<pii> vec[1'001];
void printDist(){
for(int i=1; i<=N; i++){
if(DIST[i] != MAX){
cout << "[" << i << "] : " << DIST[i] << " ,,, ";
}else{
cout << "[" << i << "] : " << "MAX" << " ,,, ";
}
}
cout << "\n";
}
void printMap(){
cout << "Map Size : " << m.size() << "\n";
for(auto itr : m){
cout << "{" << itr.first << ", " << itr.second.first << "} : " << itr.second.second << "\n";
}
}
void printAns(){
cout << m.size() << "\n";
for(auto itr : m){
cout << itr.first << " " << itr.second.first << "\n";
}
}
void init(){
cin >> N >> M;
for(int i=0; i<M; i++){
int A, B, C;
cin >> A >> B >> C;
vec[A].push_back({B,C});
vec[B].push_back({A,C});
}
}
void dijkstra(){
for(int i=0; i<=N; i++){
DIST[i] = MAX;
}
priority_queue<pii, vector<pii>, greater<>> pq;
pq.push({0, 1}); // {dist, location}
DIST[1] = 0;
while (!pq.empty()){
int curNode = pq.top().second;
int dist = pq.top().first;
pq.pop();
if(DIST[curNode] < dist) continue;
for(int i=0; i<vec[curNode].size(); i++){
int nexNode = vec[curNode][i].first;
int nexDist = vec[curNode][i].second + dist;
if(DIST[nexNode] > nexDist){
auto itr = m.find(nexNode);
if(itr == m.end()){
m.insert({nexNode, {curNode, nexDist}});
}else{
itr->second.first = curNode;
itr->second.second = nexDist;
}
DIST[nexNode] = nexDist;
pq.push({nexDist, nexNode});
}
}
}
// printDist();
// printMap();
printAns();
}
int main(){
init();
dijkstra();
return 0;
}다양한 출력함수들이 있으니 직접 실행해보아도 좋을 것 같다.
Summary
- 간선을 기억하기 위해 map을 이용하는 방법
