[백준] 동방 프로젝트(large)

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

14595번: 동방 프로젝트 (Large)

유니온-파인드를 활용하여 해결하였습니다. 범위가 입력으로 들어오면 범위 안에 있는 방들을 합쳐주어야하는데 이미 합쳐진 방들을 다시 합치는 경우를 위해서 합쳐진 방의 대표 방을 정하고 대표 방이 합쳐진 방들의 범위를 range_dict에 저장하게 됩니다. 따라서 방을 합쳐줄 때에도 대표방이 포함하고 있는 방들을 뛰어넘어서 합쳐주어야 시간초과를 피할 수 있습니다.

 

import sys
from collections import defaultdict
sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n = int(input())
m = int(input())

range_dict = defaultdict(list)

parent = [
    x for x in range(n + 1)
]

for i in range(n + 1):
    range_dict[i] = [i, i]

def find(p):
    if parent[p] == p:
        return p
    parent[p] = find(parent[p])
    return parent[p]

for _ in range(m):
    a, b = tuple(map(int, input().split()))
    # 각 방이 속한 집합을 얻어온다.
    pa = find(a)
    pb = find(b)

    if pa == pb:
        continue

    update = 0

    # 각 집합의 시작과 끝을 체크해둔다.
    start, end = 0, 0
    if pa < pb:
       start = pa
       end = pb
       update = pa
    else:
        start = pb
        end = pa
        update = pb

    index = start

    # 각 집합의 부모를 업데이트 시켜준다.
    while index <= end:
        parent[index] = update
        s, e = range_dict[index]
        index = e + 1

    range_dict[update] = [a, b]

ans = set()
for i in range(1, n + 1):
    ans.add(find(parent[i]))

print(len(ans))

 

정렬을 활용하면 더 빠른 시간에 풀이가 가능합니다. 가장 왼쪽 방을 기준으로 정렬을 해주면 왼쪽부터 합쳐지게 되는데 만약 다른 범위를 포함하는 경우가 있으면 계속해서 포함시켜주면 됩니다. 그렇지 않으면 서로 다른 집합에 속하는 방이므로 현재까지 합쳐주었던 방을 토대로 계산을 해주고 새로운 방을 합쳐주면 됩니다.

 

import sys
#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n = int(input())
m = int(input())

if m == 0:
    print(n)
    sys.exit(0)

range_list = [
    tuple(map(int, input().split()))
    for _ in range(m)
]

range_list.sort()

standard_st, standard_end = range_list[0]

ans = n

for cur_st, cur_end in range_list:
    if standard_end >= cur_st:
        standard_end = max(standard_end, cur_end)
    else:
        ans -= (standard_end - standard_st)
        standard_st, standard_end = cur_st, cur_end
ans -= (standard_end - standard_st)
print(ans)