[Python] 백준 17619) 개구리 점프

🔗문제 링크

17619번: 개구리 점프

✅ 문제 유형

라인 스위핑, 유니온 파인드, 정렬

유니온 파인드가 궁금하다면 ? → 유니온 파인드

🤔 문제 풀이

개구리가 점프해서 통나무를 건널 수 있는지를 판단하는 문제입니다. 개구리가 점프하는 조건은 통나무의 y좌표에 상관없이 수직 방향으로 뛸 수 있습니다. 그러므로 통나무 A와 통나무 B끼리 겹치는 x좌표가 있어야지 서로 건널 수 있게 됩니다.

그렇다면 유니온 파인드로 어떻게 문제를 풀 수 있을까요? 유니온 파인드는 집합 알고리즘입니다. 서로 건널 수 있다면 같은 집합으로 분류하고 건널 수 없다면 다른 집합으로 분류하면 됩니다.

🚀 문제 해결

통나무를 정렬하고 이웃한 통나무끼리 건널 수 있는지 확인해 합집합 연산을 한다면 문제가 해결될 것으로 생각하고 아래와 같은 코드를 짰습니다

for i in range(N):

    cnum,cs,ce,cy = tree[i]
    nnum,ns,ne,ny = tree[i+1]

    if ce >= ns : # union 해야함
        merge(cnum,nnum)

여기서 저는 이웃한 통나무끼리 통나무를 건널 수 있는 조건을 비교해 합집합 연산을 하는 것이 아니라 현재 집합에서 통나무가 가장 오른쪽으로 뻗어있는 길이를 사용해 조건을 비교해야 하는 것을 깨닫고 코드를 아래와 같이 수정했습니다 🙂🙂🙂

for i in range(N):
    cnum,cs,ce,cy = tree[i]
    MAXEND = max(ce,MAXEND)
    nnum,ns,ne,ny = tree[i+1]

    if MAXEND >= ns : # 통나무1이 속한 집합에서 통나무2로 건널 수 있다. 합집합 연산 실행 
        merge(cnum,nnum)

📖 코드

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

def find(x): # 자신이 속한 집합을 찾는다
    if arr[x] == x :
        return x

    arr[x] = find(arr[x])
    return arr[x]

def merge(a,b):
    a = find(a)
    b = find(b)

    if a != b: # 다른 집합이라면 합집합 연산 수행
        MIN,MAX = min(a,b) , max(a,b)
        arr[MAX] = MIN

arr=[i for i in range(N+1)]
tree =[[i,0,0,0] for i in range(N+1)]

for i in range(1,N+1):
    a,b,c = map(int,input().split())
    tree[i][1],tree[i][2],tree[i][3] = a,b,c

tree.sort(key = lambda x : x[1]) # 통나무의 시작 지점 순으로 정렬

MAXEND = 0

for i in range(N):
    cnum,cs,ce,cy = tree[i]
    MAXEND = max(ce,MAXEND)
    nnum,ns,ne,ny = tree[i+1]

    if MAXEND >= ns : # 통나무1이 속한 집합에서 통나무2로 건널 수 있다. 합집합 연산 실행 
        merge(cnum,nnum)

for i in range(1,N+1):
    find(i)

for i in range(Q):
    a,b = map(int,input().split())

    if arr[a] == arr[b]: # 같은 집합이라면 통나무를 건널 수 있다.
        print(1)
    else:
        print(0)