[백준/BOJ] 백준 3780번 : 네트워크 연결

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

3780번: 네트워크 연결

유니온 파인드를 활용하여 문제를 해결했다. 파인드에서 node의 최고 위의 노드를 찾는데, 가장 위 노드를 찾고 돌아오면서 거치는 노드들의 dist[]를 센터까지의 거리로 갱신하고 parent[]도 최고 위의 노드로 갱신한다

 

#include <iostream>
#include <algorithm>
#include <stdlib.h>
using namespace std;

int tc;
int n;
int parent[20001];
int dist[20001];

void Pre()
{
	for (int i = 1; i <= 20000; i++)
	{
		parent[i] = i;
		dist[i] = 0;
	}
}

//node의 최고 위의 노드를 찾는다
//가장 위 노드를 찾고 돌아오면서 거치는 노드들의 dist[]를 센터까지의 거리로 갱신하고 parent[]도 최고 위의 노드로 갱신한다
int Find(int node)
{
	if (parent[node] == node)
		return node;

	int parent_node = Find(parent[node]);
	dist[node] += dist[parent[node]];
	parent[node] = parent_node;

	return parent_node;
}

//node1를 node2에 연결한다
void Merge(int node1, int node2)
{
	parent[node1] = node2;
	dist[node1] = abs(node1 - node2) % 1000; //dist[node1]에 방금 node1을 연결한곳 까지 라인 길이를 저장한다 
}

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

	char command;
	int I, J;

	cin >> tc;

	for (int i = 0; i < tc; i++)
	{
		Pre();

		cin >> n;

		while (1)
		{
			cin >> command;

			if (command == 'O')
				break;

			if (command == 'E')
			{
				cin >> I;
				Find(I);
				cout << dist[I] << "\n";
			}

			else if (command == 'I')
			{
				cin >> I >> J;
				Merge(I, J);
			}
		}
	}

	return 0;
}