strutive07 블로그

BOJ 3780 네트워크 연결

 
  • 2019년 02월 16일

간단히 Disjoint set 으로 풀면 된다.

Disjoint set 에서 달라지는점이 2가지 있는데, 문제에서 가장 중요한 length 와 연결 방향이 주어진다는것이다.

length 계산을 위해서 length 배열을 만든다.

여기서 lenght 란, 현재 노드에서 최신 상태의 root 까지의 거리인데,

초기 상태에서 root 는 자기 자신이므로 lenght 는 0이다.

하지만 각 노드가 합쳐지는 merge 연산이 발생하면

root <> root 사이에 I – J (mod 1000) 만큼의 길이가 생긴다.

따라서 merge 할때 발생하는 길이를 설정해주고, 하위 Node가 호출되면 Segment tree 의 최적화 기법중 하나인 Lazy-propagation 처럼 필요할때 값을 끌어와서 사용해주면 된다.

(물론 Lazy-propagation처럼 중간에 멈추는것은 아니지만,root 가 갱신되면 tree의 위에서부터 값이 내려오는게 비슷하다.)

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;
#define INF 987654321
#define MOD 1000

int parent[20005], len[20005];

void init(int n) {
	for (int i = 0; i <= n; i++) {
		parent[i] = i;
		len[i] = 0;
	}
}

int find(int x) {
	if (x == parent[x])
		return x;
	int cur_parent = find(parent[x]);
	len[x] += len[parent[x]];
	// 기존 union-find 코드에서 length 업데이트 코드가 추가되었다.
	// 클러스터 A 에서 최신 상태의 root, 즉 센터 까지의 cost 를 재귀적으로 더한다.
	return parent[x] = cur_parent;
}

void merge(int i, int j) {
	len[i] = abs(i - j) % MOD;
	parent[i] = j;
	// union-find 같지만, 무조건 i 를 j 로 연결하는것이므로
	// tree 가 skewed 되는것을 막는 로직을 넣을필요 없다. 그냥 연결하면 된다.
}


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

	int _T = 0;
	cin >> _T;
	while (_T--)
	{
		int n;
		cin >> n;
		init(n);
		while (1) {
			char command;
			cin >> command;
			if (command == 'E') {
				int i;
				cin >> i;
				find(i);
				// find 를 해줘야하는 이유는? 
				// merge에서 len 을 업데이트 하는것은, root 끼리만 업데이트 하는것이므로
				// 하위 node들은 root 끼리 merge 되기 전의 state를 유지하고있으므로
				// 이 state 최신상태로 바꾸어주기 위함이다.
				cout << len[i] << "\n";
			}
			else if (command == 'I') {
				int i, j;
				cin >> i >> j;
				merge(i, j);
			}
			else if (command == 'O') {
				break;
			}
		}
	}

	return 0;
}

네트워크 연결

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 948 245 158 24.688%

문제

종빈이는 아주 큰 그룹의 총수다. 이 그룹은 1부터 N번까지의 번호로 구분할 수 있는 N개의 기업을 운영하고 있다. 현재 각 기업은 서로 독립적인 자체 컴퓨팅 및 통신센터를 가지고 있다.

어느 날 종빈이는 계열사의 CTO인 서현이에게 서비스 개선을 위해 각 기업의 서버를 네트워크로 연결하여 단일 통신센터에서 관리 가능한 클러스터 형태로 구성할 것을 제안했다. 종빈이의 제안을 들은 서현이는 다음과 같은 병합 과정을 고안해냈다.

  1. 클러스터 A를 제공하는 기존에 존재하는 센터 I를 고른다.
  2. 클러스터 B를 제공하는 기업 J를 고른다. B는 A가 아닌 임의의 클러스터이며, J는 센터가 아닐 수 있다.
  3. I와 J를 통신 라인으로 연결한다. 이때 기업 I와 J를 잇는 라인의 길이는 I – J (mod 1000)이다.
  4. 위 방식을 통해 클러스터 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
검색