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

문제!!

풀이 🌷

통나무의 세로로 입력으로 들어오지만 가로만 봐주면 된다.
선 긋는 스위핑 문제처럼 풀면 되는 것이었다.
그 문제 포스팅은 여기..ㅎㅎ

어려웠던 점 🦄

1. 처음에는 통나무의 가로, 세로 좌표 둘 다 봐줘야 하는 줄 알았다.. 좌표는 10^9까지 있다고 하는데, 가로 세로를 고려해서 2차원으로 만들면 너무 클 것 같은데... ㅠ 어떻게 하나 고민했다. 그런데 가로!!!만 봐주면 되는 것이었다. 점프하면 되니까 세로는 볼 필요가 없었다.
2. 원래 입력 받은 리스트를 정렬해서, 그 순서가 망가진다.. 그러니까 원래 인덱스를 가지고 있어야 한다! 그래야 어떤 통나무랑 다른 통나무랑 이어져있는지 체크가 가능하니까!!!

코드 🐸

import sys

input = sys.stdin.readline

N, Q = map(int, input().split())

line = [[*map(int, input().split())] + [i] for i in range(1, N + 1)]  # 원래 인덱스를 저장해야 하므로!!
line.sort(key=lambda x: (x[0], -x[1]))

connect = [0] * (N + 1)

right = line[0][1]
idx = 0
for i in range(1, N):
    a, b = line[i][0], line[i][1]
    if right < a:  # 안 겹칠 때
        right = b
        idx += 1
        connect[line[i][3]] = idx

    elif right < b:  # 겹칠 때
        right = b
        connect[line[i][3]] = idx  # 원래 인덱스 위치에 저장
    elif b <= right:  # 겹칠 때
        connect[line[i][3]] = idx  # 원래 인덱스 위치에 저장

for _ in range(Q):
    x1, x2 = map(int, input().split())
    if connect[x1] == connect[x2]:
        print(1)
    else:
        print(0)