🤔접근

Union-Find를 공부했다면 문제를 보는 순간 해당 방법으로 접근했을 것이다. 왜냐하면 벽을 허무는 순간 각 동방은 같은 집합에 속하기 때문이다. 그러면 가장 먼저 x번 방부터 y번 방을 허물 때, (x, x+1), (x+1, x+2), ... 로 묶어 x와 y의 부모가 다른 경우에만 합집합(union) 연산을 수행하면 된다는 것을 떠올렸을 것이다.

하지만 이 방법은 합집합 연산을 이미 수행한 부분을 매번 탐색할 수도 있기 때문에 시간초과가 난다(N은 최대 1,000,000). 이는 구간들을 최대한 묶어 한 번에 처리하는 방법을 사용하여 해결할 수 있다. 마치 그리디 문제의 대표격인 회의실 배정 풀이처럼 말이다. 다시 말해, (1,4), (2,5), (5,7) 과 같은 구간들이 있다면 이를 (1,5), (5,7) 구간으로 묶는 것이다.

😎풀이

import sys
input=sys.stdin.readline

n=int(input().rstrip())
m=int(input().rstrip())
acts=[]
for _ in range(m):
    acts.append(list(map(int,input().rstrip().split())))
acts.sort(key=lambda x:x[0])

p=[i for i in range(n+1)]

def find(x):
    if p[x]!=x:
        p[x]=find(p[x])
    return p[x]

def uni(a,b):
    a=find(a)
    b=find(b)
    if a<b:
        p[b]=a
    else:
        p[a]=b

merged_acts = []
for act in acts:
    # 첫 번째 원소인 경우 처리 
    if not merged_acts:
        merged_acts.append(act)
    else:
        # 마지막 원소 기준으로
        last = merged_acts[-1]
        # 현재 원소의 start가 마지막 원소의 end보다 작은 경우는 겹치는 방이 있다는 의미
        if act[0] < last[1]:
            # 두 구간의 end 중 최댓값을 사용하여 병합
            last[1] = max(last[1], act[1])
        else:
            # 그렇지 않으면 새로운 구간으로 추가
            merged_acts.append(act)

for s,e in merged_acts:
    for i in range(s,e):
        uni(i,i+1)

print(len(set(p[1:])))