[개구리 점프/G3/Python3]

17619번 개구리 점프 G3

 

문제
통나무 N개가 가로 (수평) 방향으로 연못에 떠 있다. 개구리는 한 통나무 A에서 다른 통나무 B로 정확히 수직 방향으로 점프할 수 있다. 단, 점프할 때 다른 통나무 위를 (끝 점 포함) 지나면 안 된다. (통나무 위에서 걸어서 움직이는 것은 언제든 가능하다.) 통나무들의 위치를 입력받아 질문으로 주어진 통나무들의 쌍에 대해서 개구리가 한 통나무에서 다른 통나무로 한번 이상의 점프로 이동이 가능한지 판단하는 프로그램을 작성하라.

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

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

 

자료 구조, 정렬, 분리 집합, 스위핑

 

위 문제를 풀기 위해 통나무로 점프 가능한 조건을 일반화시켜서 생각해 보았다.

 

문제에 따르면 서로 다른 통나무는 끝점을 포함해서 만나지 않는다.

y가 같더라도 x1, x2가 겹치거나, 맞닿는 상황이 존재하지 않는 것이다.

 

점프는 끝점에서 수직으로 점프해도 이동할 수 있다.

 

단, 점프할 때 다른 통나무 위를 (끝 점 포함) 지나면 안 된다.

위 규칙으로 인해, x1과 x2의 일부분이 겹치더라도 갈 수 없는 경우를 찾아보았지만, 두 통나무 사이에서 가로막는 통나무도 건널 수 있는 부분이 겹친 상태이기 때문에 (즉 건너는 것이 가능한 상태) 해당 경우는 존재하지 않다고 판단했다.

해당 통나무를 통해서 또 점프하면 되는 상태이기 때문이다.

 

x1을 기준으로 오름차순 정렬한 상태에서 i번 통나무에서 i+1번 통나무를 건너려면 i번으로 이동 가능한 그룹의 x2의 최댓값이 i+1보다 크거나 같으면 가능한 것으로 일반화할 수 있다.

 

즉, 이전 그룹의 max(x2)가 특정 통나무의 x1보다 크거나 같으면 해당 통나무는 건널 수 있는 상태이다.

 

 

파이썬의 정렬 함수와 분리 집합 Union Find 알고리즘을 사용하여 풀이했다.

 

import sys
sys.setrecursionlimit(10**5)
n, m = map(int, sys.stdin.readline().split())

p = [i for i in range(n+1)]

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

def union(v1, v2):
    r1, r2 = find(v1), find(v2)
    p[r1] = r2

def is_can(v1, v2):
    return int(find(v1) == find(v2))

bridge = []
for v in range(1, n+1):
    s, e, y = map(int, sys.stdin.readline().split())
    bridge.append((s,e,y,v))
bridge.sort()

le = bridge[0][1]
lv = bridge[0][3]

for i in range(1, n):
    s, e, y, v = bridge[i]
    if s <= le:
        union(v, lv)
    le = max(e, le)
    lv = v
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    print(is_can(a, b))

 

 

---

 

x1, x2이 겹치는 부분이 존재하는 통나무 사이에 무수히 많은 통나무가 존재하더라도, 3개의 통나무만 보면 결국 모두의 통나무가 이동 가능하다는 것을 알 수 있다.

1 -> 2가 가능, 2 -> 3이 가능 = 1 -> 3이 가능... 최종적으로 사이에 존재하는 모든 통나무는 이동 가능

 

해당 논리를 떠올리고 난 후에는 분리집합을 이용하여 풀이를 진행했다.

분리 집합이 아니더라도, 소속된 통나무인지 구분할 방법만 있다면 정답을 구할 수 있다.