백준 17619 [개구리 점프] 파이썬

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

 

# 백준 17619 개구리 점프
import sys
sys.setrecursionlimit(10**7)  # 재귀 깊이 제한 해제 (Union-Find에서 find 호출 때문에 필요)
input = sys.stdin.readline

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

# Union 함수 : 두 구간 [start_a, end_a], [start_b, end_b]를 병합
def union(a, b):
    a = find(a)
    b = find(b)

    if a != b:
        start_a, end_a, idx_a = range_pos[a]
        start_b, end_b, idx_b = range_pos[b]
        # 두 구간이 겹치는 경우 -> 병합
        if start_b <= end_a and start_a < end_b:
            # 겹친 두 구간을 합쳐서 [min(start), max(end)]로 확장
            range_pos[b] = (min(start_a, start_b), max(end_a, end_b), idx_b)
            parent[a] = b  # 대표 노드를 b로 설정
        elif start_a <= end_b and start_b < end_a:
            range_pos[b] = (min(start_a, start_b), max(end_a, end_b), idx_b)
            parent[a] = b

# 두 통나무가 같은 그룹(즉, 같은 연결 구간)에 속하는지 확인
def is_in(a, b):
    return find(a) == find(b)

# 입력
N, Q = map(int, input().split())
parent = [i for i in range(N+1)]   # Union-Find parent 배열
range_pos = [(-1, -1, -1)]         # 각 통나무의 (시작점, 끝점, 고유번호), dummy -1 추가
sort_nums = {}                     # 통나무 고유번호 → 정렬된 인덱스 매핑

# 통나무 정보 입력
for i in range(1, N+1):
    start, end, y_pos = map(int, input().split())
    range_pos.append((start, end, i))

# x좌표 시작점을 기준으로 정렬
range_pos.sort(key=lambda x: x[0])

# 통나무 고유번호(idx) → 정렬된 위치로 매핑
for i in range(1, N+1):
    sort_nums[range_pos[i][2]] = i

# 인접한 통나무끼리 union (겹치면 합쳐짐)
for i in range(1, N):
    union(i, i+1)

# 질의 처리
for _ in range(Q):
    a, b = map(int, input().split())
    a = sort_nums[a]   # 입력으로 받은 통나무 번호를 정렬된 인덱스로 변환
    b = sort_nums[b]
    print(int(is_in(a, b)))  # 같은 그룹이면 1, 아니면 0 출력

잘 짜놓고, 이상한 점을 기준으로 정렬을 해버렸다.. (x시작기준이어야하는데, idx를 기준으로 정렬해버렸다)

 

해메다가 결국 찾아 해결하였다.

 

UNION-FIND 더 익숙해지자