[C++] 백준 24391번: 귀찮은 해강이

문제 링크

24391번: 귀찮은 해강이

문제 요약

특정한 건물들 사이에는 통로가 있다. 건물들을 이동할 때, 최대한 통로를 이용해서 실내로 이동을 하고자 한다. 이때, 불가피하게 건물을 나와서 이동해야하는 횟수를 출력해야 한다

접근 방법

문제를 읽자마자 유니온파인드를 사용하면 된다고 생각했습니다. 유니온파인드를 이용해서 통로로 연결된 건물들을 하나의 set으로 묶습니다. 그리고 건물의 이동순서를 따라가면서 인접한 순서의 건물이 다른 set에 있으면 카운트해주는 식으로 구현하면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 100001;
int parent[MAX];

int Find(int a)
{
	if (a == parent[a])
		return a;
	return parent[a] = Find(parent[a]);
}

void Union(int a, int b)
{
	int pa = Find(a), pb = Find(b);
	parent[pa] = pb;
}

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

	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		parent[i] = i;

	for (int i = 0; i < m; i++)
	{
		int b1, b2;
		cin >> b1 >> b2;
		Union(b1, b2);
	}

	vector<int> v(n);
	for (int i = 0; i < n; i++)
		cin >> v[i];

	int cnt = 0;
	for (int i = 0; i < n - 1; i++)
		if (Find(v[i]) != Find(v[i + 1]))
			cnt++;

	cout << cnt << '\n';
	return 0;
}