백준 온라인 저지, 그리디 / 17619번: 개구리점프 (파이썬 / 백준 골드문제)

문제

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

문제 정의

통나무 N개가 가로 (수평) 방향으로 연못에 떠 있다. 개구리는 한 통나무 A에서 다른 통나무 B로 정확히 수직 방향으로 점프할 수 있다. 단, 점프할 때 다른 통나무 위를 (끝 점 포함) 지나면 안된다.
예를 들어 <그림 1>에서 1번 통나무에서 2번 통나무로 점선을 따라 개구리가 점프하는 것이 가능하다. 1번 통나무에서 2번 통나무로 점프한 후 다시 3번 통나무로 점프하면 1번 통나무에서 3번 통나무로 이동하는 것이 가능하다. (통나무 위에서 걸어서 움직이는 것은 언제든 가능하다.)

<그림 1>
통나무들의 위치를 입력받아 질문으로 주어진 통나무들의 쌍에 대해서 개구리가 한 통나무에서 다른 통나무로 한번 이상의 점프로 이동이 가능한지 판단하는 프로그램을 작성하라.

입력

첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 다음 N개의 줄에 각 통나무에 x1, x2, y의 세 정수 좌표가 주어진다. 주어진 통나무는 두 점 (x1, y)와 (x2, y)를 잇는 형태이다. (x1 < x2) 모든 좌표는 0이상 109이하이다. 통나무들은 주어진 순서대로 1번부터 번호가 붙어 있다. 서로 다른 두 통나무는 (끝점에서도) 만나지 않는다. 다음 Q개의 줄에 서로 다른 두 통나무의 번호가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ Q ≤ 100,000)

출력

Q개의 줄을 출력한다. 각 줄에는 주어진 순서대로 질문에 대한 대답이 출력되어야 한다. 질문에 주어진 두 통나무에 대해서 개구리가 한 통나무에서 다른 통나무로 한번 이상의 점프로 이동이 가능한 경우 대답은 1, 그렇지 않은 경우 대답은 0이다.

예제 입력 1

4 2
1 5 2
3 7 4
7 9 1
10 13 4
1 3
1 4

예제 출력 1

1
0

접근 방법

- 각 통나무에 대한 정보를 입력받을 때 x1, x2, y로 받은 값을 x1, x2, 통나무 번호로 저장한다. y를 저장하지 않는 이유는 x의 값이 겹칠 경우 y와 상관없이 이동할 수 있기때문이다.
- 각 통나무의 번호를 인덱스로 하고 스위핑으로 묶일 수 있는 집합의 번호를 값으로 하는 dp테이블을 초기화한다.
- 통나무에 대한 정보를 x1을 기준으로 오름차순 정렬하고 이를 하나씩 탐색하며 스위핑으로 묶이는 집합을 dp테이블에 입력한다.
- 각 Q에 대해 인덱스를 탐색하며 같은 값이면 1아니면 0을 출력한다.

코드

# https://www.acmicpc.net/problem/17619
# 접근 방법
# 각 통나무에 대한 정보를 입력받을 때 x1, x2, y로 받은 값을 x1, x2, 통나무 번호로 저장한다. y를 저장하지 않는 이유는 x의 값이 겹칠 경우 y와 상관없이 이동할 수 있기때문이다.
# 각 통나무의 번호를 인덱스로 하고 스위핑으로 묶일 수 있는 집합의 번호를 값으로 하는 dp테이블을 초기화한다.
# 통나무에 대한 정보를 x1을 기준으로 오름차순 정렬하고 이를 하나씩 탐색하며 스위핑으로 묶이는 집합을 dp테이블에 입력한다.
# 각 Q에 대해 인덱스를 탐색하며 같은 값이면 1아니면 0을 출력한다.
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
log = []

for i in range(1, n+1):
    x1, x2, y = map(int, input().split())
    log.append([x1, x2, i])
    
dp = [0] * (n+1)

log.sort(key=lambda x: x[0])

number = 1
end = log[0][1]

for x1, x2, i in log:
    if end < x1:
        number += 1
        end = x2
    else:
        end = max(end, x2)
    dp[i] = number

for i in range(q):
    x1, x2 = map(int, input().split())
    if dp[x1] == dp[x2]:
        print(1)
    else:
        print(0)