[Python] 백준 17619번: 개구리 점프

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

17619번: 개구리 점프

 

1. 통나무의 높이는 크게 상관이없다. 통나무끼리의 길이만 겹쳐있으면 어디로든지 이동할수있다.

2. 처음에 x길이를 기준으로 정렬을 해준다.

3. union & find로 길이가 겹치면 이전노드로 현재노드를 묶어주고 ny길이값을 갱신해준다(처음에 정렬했기때문에 x값은 고정).

4. 길이가 겹치지않으면 nx, ny 값을 다음 x, y 값으로 초기화해준다.

5. 입력을 N 100,000개 Q 100,000개이므로 기존input()으로 입력을 받으면 시간초과가 난다.

(참고)

https://www.acmicpc.net/blog/view/57

출력 속도 비교

import sys
n, m = map(int, input().split())
log = [[-1, -1, 0]]
parent = [i for i in range(n+1)]

def find(x):
    if x == parent[x]:
        return x
    else:
        parent[x] = find(parent[x])
        return parent[x]

def union(x, y):
    x = find(x)
    y = find(y)
    if x < y:
        parent[y] = x
    else:
        parent[x] = y

for i in range(n):
    s, e, h = map(int, sys.stdin.readline().rstrip().split())
    log.append([s, e, i+1])

log.sort(key=lambda x: (x[0], x[1]))
x, y, _ = log[1]
for i in range(2, len(log)):
    nx, ny, _ = log[i]
    if nx <= y:
        union(log[i-1][2], log[i][2])
        y = max(y, ny)
    else:
        x, y = nx, ny

for _ in range(m):
    s, e = map(int, sys.stdin.readline().rstrip().split())
    if find(s) == find(e):
        print(1)
    else:
        print(0)