[백준] 17619. 개구리 점프

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

17619번: 개구리 점프

통나무를 받은 순서대로 통나무의 번호가 매겨지므로, 통나무를 받을 때 좌표와 함께 idx를 저장한다. 그러면 통나무 리스트에는 [x1, x2, y, 통나무 번호]가 들어있게 된다. 이렇게 받은 리스트를 통나무의 x1 (제일 첫부분 좌표)로 정렬해준다.

 

만약 [[4, 9, 3, 0], [3, 5, 7, 1], [1, 3, 5, 2]] 과 같은 arr가 만들어졌을때 x1을 기준으로 정렬하면 [[1, 3, 5, 2], [3, 5, 7, 1], [4, 9, 3, 0]]이 되고 이는 아래와 같은 그림을 표현할 수 있게 된다.

처음에 위치한 통나무의 번호와, 끝 x좌표를 각각 p_idx(부모 통나무 번호)와 x_end에 저장하고 x좌표 순서대로 통나무를 확인하며 부모 통나무의 끝좌표와 현재 통나무의 시작 좌표가 겹치면 같은 집합으로 표시(점프 가능)하고, 부모 통나무의 끝 좌표와 현재 통나무의 끝 좌표중 더 큰 좌표값으로 갱신해준다. 이때 p_idx는 여전히 부모 통나무의 번호이다. 좌표가 계속 겹친다면 부모 통나무에서부터 점프가 가능하기 때문이다. 만약 통나무가 겹치지 않는다면, 통나무의 끝좌표와 부모 통나무 번호를 갱신해준다.

 

이렇게 만들어진 통나무의 부모 리스트를 이용해 입력으로 들어온 통나무가 서로 같은 부모를 갖고 있다면 점프가 가능하므로 1을, 아니라면 0을 print 해준다.

import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
arr = [list(map(int, input().split())) + [i] for i in range(N)]
arr.sort(key=lambda x: x[0]) # 통나무 정렬
p = [i for i in range(N)] # 부모

p_idx = arr[0][3] # 처음에 위치한 통나무의 idx
x_end = arr[0][1] # 처음에 위치한 통나무의 제일 끝 부분

for i in range(1, N):
    # 이전 통나무의 제일 끝부분 x좌표보다 현재 통나무의 제일 첫부분 x좌표가 작으면 점프로 이동 가능
    # 부모가 같다 (같은 팀이다)
    # 현재 본 통나무의 제일 끝부분과 이전 통나무 제일 끝부분 중 더 긴 것으로 갱신
    if x_end >= arr[i][0]:
        x_end = max(x_end, arr[i][1])
        p[arr[i][3]] = p_idx
    # 아니라면 이동 불가능, 서로 다른 부모
    else:
        p_idx = arr[i][3]
        x_end = arr[i][1]

for _ in range(Q):
    x, y = map(int, input().split())
    if p[x-1] == p[y-1]: # 부모가 같음 == 점프 가능
        print(1)
    else:
        print(0)