[백준] 골드4 : (24391) 귀찮은 해강이

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

 

분리 집합(Union-Find)으로 푸는 문제이다.

문제의 제한시간이 0.5초인데, 입력의 제한이 최대 100,000이기 때문에 최소 O(n log₂ n) 정도가 나와야 한다.

 

처음에 이어져있는 건물들이 나열될 때, 입력이 주어질 때마다 Union을 해주면, 다음 입력에 부모가 같은 입력이 나왔을 때 시간을 절약할 수 있다.

 

Union이 모두 끝났으면, 정답을 출력할 입력을 차례대로 받는다.

두 건물 사이를 이동하는 횟수를 구하는 것이므로, 입력으로 사용할 변수를 두 개 선언한다. (현재 건물, 이동할 건물)

맨 처음 강의를 들으러 이동하는 횟수는 세지 않으므로, 현재 건물 변수의 입력을 먼저 받는다.

순회를 돌며, 다음으로 이동할 건물의 입력만 받고, 현재 건물과 이동할 건물의 부모를 비교하여 검사한다.

마지막에는 현재 건물을 이동할 건물로 초기화해줘야 한다.

#include <iostream>
#include <vector>
using namespace std;

vector<int> Parent;

int Find(int n)
{
	if (Parent[n] == n) return n;
	return Parent[n] = Find(Parent[n]);
}

void Union(int a, int b)
{
	a = Find(a);
	b = Find(b);
	if (a != b) Parent[b] = a;
}

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

	int N, M, Answer = 0;
	cin >> N >> M;

	// 각자 자기 자신을 부모로 초기화
	Parent.resize(N + 1);
	for (int i = 1; i <= N; ++i) Parent[i] = i;

	// 이어져있는 건물의 입력이 나올 때 마다 Union 해줌
	for (int i = 0, j, k; i < M; ++i)
	{
		cin >> j >> k;
		Union(j, k);
	}

	int j, k;
	cin >> j; // 첫 입력 받음
	for (int i = 0; i < N - 1; ++i)
	{
		cin >> k;

		// 현재 건물과 다음 강의의 건물이 이어져있는지 검사
		if (Find(Parent[j]) == Find(Parent[k]))
		{
			j = k;
			continue;
		}
		Answer++; // 이어져있지 않으면 1 증가

		j = k;
	}

	cout << Answer << "\n";
}