백준 24391 : 귀찮은 해강이 (Python)

본문 링크

import sys
input=sys.stdin.readline

def Find(x):

    if x!=disjoint[x]:
        disjoint[x]=Find(disjoint[x])
    return disjoint[x]

def Union(a,b):

    a=Find(a)
    b=Find(b)

    if a>b:
        disjoint[a]=b
    else:
        disjoint[b]=a

N,M=map(int,input().split())

disjoint=[0]*(N+1)

for i in range(1,N+1):
    disjoint[i]=i


for i in range(M):

    a,b=map(int,input().split())
    Union(a,b)

L=list(map(int,input().split()))
total=0
for i in range(1,len(L)):

    if Find(L[i-1])!=Find(L[i]):
        total+=1

print(total)

📌 어떻게 접근할 것인가?

유니온 파인드 기초 문제입니다.

문제에서 강의실 시간표가 주어졌을때 해강이가 밖에 나와야 하는 최소 횟수 를 구하는 것입니다.

유니온 파인드를 사용해서 , 새로운 강의가 나타났을때 다른 집합에 있다면 $+1$ 을 해주면 됩니다.

이는

for i in range(1,len(L)):

    if Find(L[i-1])!=Find(L[i]):
        total+=1

으로 구현할 수 있습니다.

유니온 파인드를 구현해주고 강의실이 속한 집합이 달라질때마다 개수를 더해주면 끝입니다.