네트워크 연결
알고리즘 구분 : 자료 구조, 분리 집합
문제
종빈이는 아주 큰 그룹의 총수다. 이 그룹은 1부터 N번까지의 번호로 구분할 수 있는 N개의 기업을 운영하고 있다. 현재 각 기업은 서로 독립적인 자체 컴퓨팅 및 통신센터를 가지고 있다.
어느 날 종빈이는 계열사의 CTO인 서현이에게 서비스 개선을 위해 각 기업의 서버를 네트워크로 연결하여 단일 통신센터에서 관리 가능한 클러스터 형태로 구성할 것을 제안했다. 종빈이의 제안을 들은 서현이는 다음과 같은 병합 과정을 고안해냈다.
클러스터 A를 제공하는 기존에 존재하는 센터 I를 고른다.
클러스터 B를 제공하는 기업 J를 고른다. B는 A가 아닌 임의의 클러스터이며, J는 센터가 아닐 수 있다.
I와 J를 통신 라인으로 연결한다. 이때 기업 I와 J를 잇는 라인의 길이는 |I – J|(mod 1000)이다.
위 방식을 통해 클러스터 A와 B는 새로운 클러스터로 합쳐지며, 이 클러스터는 B의 센터에 의해 제공된다.
이러한 병합 과정을 거치던 중에, 각 기업에서 현재 센터까지 연결되는 라인의 길이가 총 얼마나 되는지에 관한 문의가 들어왔다. 서현이를 위해 병합하는 과정과 그 과정에서 통신센터와 각 기업을 잇는 라인의 길이를 구하는 프로그램을 작성해보자.
입력
입력은 여러 개의 테스트케이스로 주어진다. 입력의 첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스에는 기업의 수를 나타내는 N(4 ≤ N ≤ 20,000)이 주어진다. 다음은 몇 개의 줄에 걸쳐 아래 두 가지 종류의 명령어가 들어온다.
E I – 기업 I와 현재 I의 센터까지의 거리를 출력한다.
I I J – 센터 I를 기업 J에 연결한다.
각 테스트케이스의 끝에는 단어 O가 주어진다. 각 테스트케이스에서 명령어의 총 개수는 200,000개를 넘지 않으며, 그중 I 명령어의 개수는 N개보다 작다.
출력
E 명령어가 들어올 때마다 한 줄에 해당 거리를 출력한다.
예제 입력 1
1
4
E 3
I 3 1
E 3
I 1 2
E 3
I 2 4
E 3
O
예제 출력 1
0
2
3
5
문제 풀이
예제를 풀어보면,
(1) E 3
Node 1 2 3 4
Cent 1 2 3 4
즉, 각자 본인이 센터가 된 상태로 미연결 상태이다.
(2) I 3 1
Node 1 2 3 4
Cent 1 2 1 4
3번 node에 부모노드가 1로 변경되었다.
(3) E 3
Node 1 2 3 4
Cent 1 2 1 4
3번 node의 연결은 1로 되어있고, 1은 자기 자신이 센터이다.
즉, dist는 abs(3 - 1) % 1000이 되어 2이 출력된다.
(4) I 1 2
Node 1 2 3 4
Cent 2 2 1 4
1번 node의 부모노드가 2로 변경되었다.
(5) E 3
Node 1 2 3 4
Cent 2 2 1 4
3번 node -> 1, 1번 node -> 2, 2번 node 자기 자신 센터
즉, dist는 (abs(3 - 1) % 1000) + (abs(1 - 2) % 1000)가 되어 3이 출력된다.
(6) I 2 4
Node 1 2 3 4
Cent 2 4 1 4
2번 node의 부모노드가 4로 변경되었다.
(7) E 3
Node 1 2 3 4
Cent 2 4 1 4
3번 node -> 1, 1번 node -> 2, 2번 node -> 4, 4번 node 자기 자신 센터
즉, dist는 (abs(3 - 1) % 1000) + (abs(1 - 2) % 1000) + (abs(2 - 4) % 1000)가 되어 5가 출력된다.
그렇기에, E 입력될 때의 함수와 I 입력될 때의 함수를 구현하는 과정을 통해서 해결하고자 했다.
int ei(int a) {
int result = 0;
int now = a;
int before = a;
while(true) {
if(parent[now] == now) {
result += (abs(now - before) % 1000);
break;
}
now = parent[now];
result += (abs(now - before) % 1000);
before = now;
}
return result;
}
void iij(int a, int b) {
parent[a] = b;
}위와 같이 I일 때는 일종의 union연산이 진행된다. 여기서 union의 방향성이 정해져 있기에 일반적인 union함수와 다르게 조건문이 붙지 않도록 구현했다.
E일 때는 자기 자신이 부모 노드가 되는 노드를 찾을 때까지 반복문으로 접근하면서 해당 이동 값들을 다 더하는 과정을 통해서 구현했다.
그러나, 문제에서 입력이 무한하며, O가 입력되기 전까지 계속 입력이 들어오게 되는데, 이는 I가 늘어나면 늘어날수록 시간 복잡도 상의 과부하가 일어나게 되어 TLE를 받게 되었다.
그렇게 되어, 질문 게시판을 보던 중, 관련 입출력 데이터를 참고할 수 있게 되어 해당 데이터를 보고, 천천히 다시 정립해갔다.
I연산으로 union연산을 진행할 때, 미리 해당 노드의 distance 계산을 진행해놓는다면, 추후 E 연산 과정에서 모듈러연산을 반복할 필요성이 사라지게 되므로, 시간복잡도를 많이 잡아먹게 되는 모듈러 연산의 횟수를 크게 절감할 수 있어 별도의 distacne 배열을 선언하여 계산을 미리해놓도록 하였다.
E연산에서는 부모노드를 찾아가는 과정이 된다. 일반적으로는 return parent[x] = findParent(parent, x);를 통해 재귀적으로 구현하게 되는데, 이렇게 되면 중간 경유 과정의 거리 계산이 무시되므로 이를 구하는 과정이 필요하다. 그렇기에,
int findParent(int parent[], int x) {
if(parent[x] != x) {
int px = findParent(parent, parent[x]);
dist[x] += dist[parent[x]];
parent[x] = px;
return parent[x];
}
return parent[x];
}위와 같이 구현하였다. 재귀적으로, findParent함수 안에서 본인의 부모 노드의 dist 배열을 참조해 본인의 dist배열을 갱신하는 과정을 구현하면 된다.
예제 입력의 7번째 줄인 E 3의 과정을 통해 설명해보자면,
Node 1 2 3 4
Dist 1 2 2 0
인 상태에서
findParent(parent, 3) 실행
findParent(parent, 1) 실행
findParent(parent, 2) 실행
findParent(parent, 4) 실행
findParent(parent, 4) 종료 (dist[4] = 0)
findParent(parent, 2) 종료 (dist[2] = 2 + 0)
findParent(parent, 1) 종료 (dist[1] = 1 + 2)
findParent(parent, 3) 종료 (dist[3] = 2 + 3)
이 되어 dist가 5로 갱신된다.
(질문 게시판이 없었다면, 위 과정을 정확하게 마무리 짓지 못했을 것 같다.)
관련 입출력 데이터 확인 사이트 : http://acm.ro/ (특이하게 https 연결 설정이 되어 있지 않은 것 같다.)
해당 홈페이지 접속하여, 좌측 list에서 past years에 들어가 SouthEastern European Regional Contest 2004를 클릭하여 problems를 클릭 후 ZIP Archive containing all the problems and data tests를 다운받아 TC를 확인하면 된다.
소스 코드
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
int t, n;
int dist[20001];
int parent[20001];
int findParent(int parent[], int x);
void iij(int a, int b);
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
memset(parent, 0, sizeof(parent));
cin >> t;
while(t--) {
cin >> n;
memset(dist, 0, sizeof(dist));
for(int i = 1; i < n + 1; i++) {
parent[i] = i;
}
while(true) {
char input;
cin >> input;
if(input == 'O') {
break;
}
if(input == 'E') {
int i;
cin >> i;
findParent(parent, i);
cout << dist[i] << endl;
}
else if(input == 'I') {
int i, j;
cin >> i >> j;
iij(i, j);
}
}
}
return 0;
}
int findParent(int parent[], int x) {
if(parent[x] != x) {
int px = findParent(parent, parent[x]);
dist[x] += dist[parent[x]];
parent[x] = px;
return parent[x];
}
return parent[x];
}
void iij(int a, int b) {
parent[a] = b;
dist[a] = abs(a - b) % 1000;
}- 문제 출처 : https://www.acmicpc.net/problem/3780
- 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.
