백준 14595 [동방 프로젝트(Large)] 파이썬

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

 

# 백준 14595 동방 프로젝트 (Large)
# 문제 요약: 
#   N개의 방이 일렬로 있고, M번의 공격이 발생한다.
#   공격은 x~y 구간의 벽을 무너뜨려 연결하는 방식으로 이루어진다.
#   최종적으로 남은 "구분된 방의 개수"를 출력하는 문제.

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N = int(input())   # 방의 개수
M = int(input())   # 공격 횟수

# parent[i] : i번 방이 속한 그룹(대표 방 번호)을 저장
parent = [i for i in range(N+1)]

# Find 함수 (경로 압축)
def find(x):
    if x != parent[x]:
        parent[x] = find(parent[x])
    return parent[x]

# Union 함수 (x~y 범위를 하나의 집합으로 합침)
def union(a, b):
    a = find(a)
    b = find(b)
    # a가 b보다 작은 동안, 즉 [a, b] 구간을 전부 합침
    while a < b:
        parent[a] = b          # a의 대표를 b로 갱신
        a = find(a+1)          # 다음 방으로 넘어가며 병합 진행

# M번 공격 실행
for _ in range(M):
    x, y = map(int, input().split())
    union(x, y)

# 최종적으로 parent[i] == i 인 경우는 "대표 방"
# 즉, 독립된 구역(방의 묶음)이 하나 있는 것
ans = 0
for i in range(1, N+1):
    if parent[i] == i:
        ans += 1

print(ans)   # 남은 방의 개수 출력

UNION-FIND를 이용하되, 경로를 압축한다.