[BOJ/Gold 4] 백준 24391 귀찮은 해강이(C++)

문제 링크

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

24391번: 귀찮은 해강이

 

문제

해강이는 앙중대학교에 다닌다. 해강이는 이번 학기에 강의코드 1번부터 N번까지 N개의 강의를 듣고 있다.

모든 강의는 강의코드와 동일한 번호의 건물에서 진행된다. 예를 들어, 강의코드가 1인 강의는 1번 건물에서 진행되고, 강의코드가 N-1인 강의는 N-1번 건물에서 진행된다.

해강이는 밖에 나오는 것을 싫어해서, 강의 시간표 순서대로 모든 강의를 들으면서 한 건물에서 밖으로 나와서 다른 건물로 이동하는 횟수를 최소화하고 싶다. 앙중대학교에는 다행히도 서로 연결되어 있는 건물들이 있어, 이 건물끼리는 밖으로 나오지 않고 이동할 수 있다.

해강이의 강의 시간표가 주어질 때, 밖에 나오는 것을 싫어하는 해강이를 위해 최소 몇 번만 밖에 나오면 되는지 구해보자. 맨 처음 강의를 들으러 이동하는 횟수는 세지 않는다.

입력

첫째 줄에 강의의 개수 N(1 ≤ N ≤ 105)과 연결되어 있는 건물의 쌍의 개수 M(0 ≤ M ≤ 105)이 공백으로 구분되어 주어진다.

두 번째 줄부터는 M줄에 걸쳐 i와 j(1 ≤ i, j ≤ N)가 주어진다. 이는 i번 건물과 j번 건물이 연결되어 있다는 의미이다. 건물이 자기 자신과 연결되거나, 이미 연결된 건물의 쌍이 다시 주어지는 경우는 없다.

마지막 줄에는 N개의 강의코드 Ai(1 ≤ Ai ≤ N)로 이루어진 강의 시간표가 공백으로 구분되어 주어진다.

출력

해강이가 밖에 나와야 하는 최소 횟수를 출력한다.

예제 입력 1

5 3
1 3
2 5
3 4
1 2 3 5 4

예제 출력 1

4

알고리즘 분류

• 유니온 파인드

풀이

건물이 연결되어 있으면 유니온 파인드로 연결한다.

그리고 첫 번째 강의부터 N-1번째 강의까지 다음 강의와 비교하면서 연결된 건물에서 진행하는 수업이 아니라면 건물을 나오는 횟수를 1 증가시킨다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100001
#define LL long long
#define INF 1e9

using namespace std;
int N, M;
int Parent[MAX];
vector<int> Timeline;
int answer = 0;

void Init() {
	for (int i = 1; i <= N; i++) {
		Parent[i] = i;
	}
}

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

void Union(int X, int Y) {
	int PX = Find(X);
	int PY = Find(Y);
	if (PX != PY) {
		Parent[PY] = PX;
	}
}

void Input() {
	cin >> N >> M;
	Init();
	for (int i = 0; i < M; i++) {
		int I, J;
		cin >> I >> J;
		if (Find(I) != Find(J)) {
			Union(I, J);
		}
	}
	for (int i = 1; i <= N; i++) {
		int A;
		cin >> A;
		Timeline.push_back(A);
	}
}

void Settings() {
	for (int i = 0; i < (N - 1); i++) {
		int Cur = Timeline[i];
		int Next = Timeline[i + 1];
		if (Find(Cur) != Find(Next)) {
			answer++;
		}
	}
}

void Find_Answer() {
	cout << answer << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}