[Gold V] 귀찮은 해강이 - 24391

문제 링크

성능 요약

메모리: 46032 KB, 시간: 296 ms

분류

자료 구조, 분리 집합, 그래프 이론, 그래프 탐색

문제 설명

해강이는 앙중대학교에 다닌다. 해강이는 이번 학기에 강의코드 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)로 이루어진 강의 시간표가 공백으로 구분되어 주어진다.

출력

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

풀이

아이디어

보자마자 Disjoint Set을 떠올린 문제.
골드 5라 그런지 위 방법만 안다면 크게 응용이랄것도 없이 풀이가 가능했음.

코드

import sys
input = sys.stdin.readline
def find(x):
    if x != parent[x]:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    a = find(a)
    b = find(b)
    if a > b:
        parent[a] = b
    else:
        parent[b] = a


lecture, connection = map(int, input().split())
parent = [i for i in range(lecture+1)]

for i in range(connection):
    union(*map(int, input().split()))

cnt = 0
timetable = list(map(int, input().split()))
current = timetable[0]
for i in timetable[1:]:
    if find(current) != find(i):
        cnt += 1
        current = i
print(cnt)

---

회고

맨 처음에 flag를 이용하여 서로 다른 집합인지 판단하는 코드를 만들었었는데 생각해보니 find를 통해 부모가 같은지만 확인해주면 되는 것이었던 것..!

재밌었다.