[백준 17619]2019 정올 2차 중등부 "개구리 점프"

문제 출처 : https://www.acmicpc.net/problem/17619

17619번: 개구리 점프

이 문제는 2019년 정보올림피아드 2차 대회 중등부 2번 문제 입니다.

문제 이해하기

이 문제는 점프를 얼마나 해서 이동할 수 있는지 묻는 문제가 아닙니다. 오직 이동이 가능한지, 불가능한지 묻는 문제 입니다. 즉 높이는 아무 상관 없이 길이가 겹쳐지는지를 따져서 연결 여부만 알 수 있으면 됩니다.

문제에서는 이렇게 길이와 높이가 나와 있지만 실제 문제 해결을 위해서는 높이가 필요 없다는 뜻입니다.

이렇게 연결되어 있는지만 확인하면 됩니다. 그래프의 연결을 확인하기 좋은 알고리즘은 유니온 파인드이고, 그것으로 이 문제를 해결 할 수 있습니다. 유니온 파인드에 대해서 잘 모른다면 아래 링크를 통해 확인 바랍니다.

https://wikidocs.net/206632

02. 유니온 파인드

문제 해결하기

이 문제를 해결하기 위한 알고리즘을 생각해보겠습니다. 높이는 상관없이 모든 통나무의 시작과 끝을 정렬하여 늘어놓습니다. 이전 통나무의 끝보다 현재 통나무의 시작이 크다면 연결이 되어있지 않은 것입니다. 이런 경우에는 시작과 끝을 새로운 통나무로 바꿔줍니다. 그렇지 않다면 이전 통나무와 현재 통나무를 연결시켜 줍니다. 이 부분이 union을 하는 부분 입니다. 그리고 끝 값을 더 긴 값으로 바꿔 줍니다. 말만으로는 이해하기 힘드니 간단한 예를 살펴 보겠습니다.

이런 형태로 통나무가 있다고 생각해 보겠습니다. 문제에서 이 통나무들이 정렬되어 있다는 말은 없습니다. 그냥 앞과 뒤의 통나무를 비교해서 연결한다고 생각해 보겠습니다. 1번과 2번 통나무는 바로 연결되어 있지 않습니다. 당연하게 연결시킬 수 없습니다.

정렬하기

연결 여부를 확인하기 위해 모든 통나무의 시작 위치를 기준으로 정렬 합니다. 모든 통나무들을 정렬을 하면 1번 다음 3번이 오고, 다음이 2번, 5, 4번순으로 정렬이 됩니다. 1번의 끝과 3번의 시작만 비교하면 두 통나무가 연결되어 있다는 것을 알 수 있습니다.

union

1번과 3번이 연결되어 있다는 것을 알게 되었으니 두 통나무를 union 합니다. 그 후 끝의 위치를 3번의 위치로 이동합니다. 이제 같은 방식으로 이전 통나무의 끝 위치와 다음 통나무의 시작 위치만 비교해서 계속 연결을 하면 됩니다.

4번 통나무의 시작은 이전 통나무의 끝보다 큽니다. 따라서 연결이 되어 있지 않습니다. 4번 통나무의 시작과 끝이 새로운 시작과 끝이 되고, 앞서 연결한 방법과 같이 뒤에 또 연결 되는 통나무가 있는지 따져보면 됩니다.

find

이렇게 모든 통나무들을 union하게되면 연결된 통나무들은 모두 같은 부모를 가지게 됩니다. 알고싶은 통나무의 부모를 찾아 부모가 같으면 1을 출력하고, 아니면 0을 출력하면 되는 문제 입니다.

코드 작성하기

그럼 문제의 코드를 작성해 보겠습니다.

입력 받기

import sys 
input = sys.stdin.readline 

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

line = []

for i in range(1, N + 1):
    s, e, _ = map(int, input().split())
    line.append((s, e, i))

N의 범위가 10만, Q의 범위가 10만 까지로 입력되는 양이 많습니다. 따라서 입력받는 속도를 높이기 위해서 readline을 사용해 주었습니다.

다음으로 통나무의 개수 N과 질문의 개수 Q를 입력 받습니다. 통나무에는 3개의 데이터를 저장합니다. 두 개의 데이터는 두 점의 시작 좌표와 끝 좌표 입니다. 그리고 마지막 세 번째는 높이가 아닌 통나무의 번호를 저장 합니다. 앞에서도 말했듯이 통나무의 높이 좌표는 필요가 없습니다. 하지만 통나무 번호로 연결 여부를 확인해야 하기 때문에 통나무의 번호는 기억하고 있어야 합니다. 그래서 시작 위치 s, 끝 위치 e, 필요없는 높이 정보 _를 입력 받고 통나무의 번호를 기억할 인덱스 i값으로 line이라는 리스트에 s, e, i를 저장 합니다.

통나무 연결하기

line.sort()
start, end, _ = line[0]
for i in range(1, N):
    nxt_start, nxt_end, nxt_idx = line[i]
    if end < nxt_start:        
        start, end = nxt_start, nxt_end
    else:
        idx = line[i - 1][2]
        union(idx, nxt_idx)
        end = max(end, nxt_end)

line을 정렬합니다. 첫 번째가 시작 위치, 두 번째가 끝 위치이기 때문에 그냥 정렬하면 통나무의 위치에 따라 정렬이 됩니다. 비교를 위한 시작과 끝 start와 end는 첫 번째 통나무 line[0]으로 저장 합니다. 다음으로 통나무가 연결 되어 있는지 확인 합니다. 현재 통나무의 끝 위치보다 새로운 통나무의 시작이 크다면 연결이 안된 것이기 때문에 start와 end값을 새로운 통나무 위치로 바꿔 줍니다.

만약 현재의 끝 위치보다 다음의 시작보다 작다면 두 통나무는 연결되어 있다는 것이고, 이 두 통나무를 union하여 연결해 줍니다. 그리고 현재의 통나무의 끝 값과 다음 통나무의 끝 값을 비교하여 더 긴 값으로 end를 바꿔 줍니다.

union 함수

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

    if a < b:
        parent[a] = b 
    else:
        parent[b] = a

union 함수 입니다. 유니온 함수에 대해서는 잘 알고 있다고 생각되어 따로 설명하지 않겠습니다. 잘 이해가 안된다면 위 링크를 통해 확인해 보시기 바랍니다.

find 함수

parent = [i for i in range(N+1)]
def find(n):
    if n != parent[n]:         
        parent[n] = find(parent[n])
    return parent[n]

find 함수 역시 잘 알고 있다 생각하고 따로 설명하지 않겠습니다.

결과 출력하기

for _ in range(Q):
    i, j = map(int, input().split())

    if find(i) == find(j):
        print(1)
    else:
        print(0)

Q개의 질문에 대한 결과를 출력하는 것입니다. find 함수를 통해 두 통나무가 연결 되어 있으면 1을 출력하고, 연결되어 있지 않으면 0을 출력하는 것입니다.

전체 코드

전체 코드를 알아보겠습니다.

import sys 
input = sys.stdin.readline 

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

line = []
for i in range(1, N + 1):
    s, e, _ = map(int, input().split())
    line.append((s, e, i))

parent = [i for i in range(N+1)]
def find(n):
    if n != parent[n]:         
        parent[n] = find(parent[n])
    return parent[n]

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

    if a < b:
        parent[a] = b 
    else:
        parent[b] = a

line.sort()
start, end, _ = line[0]
for i in range(1, N):
    nxt_start, nxt_end, nxt_idx = line[i]
    if end < nxt_start:        
        start, end = nxt_start, nxt_end
    else:
        idx = line[i - 1][2]
        union(idx, nxt_idx)
        end = max(end, nxt_end)

for _ in range(Q):
    i, j = map(int, input().split())

    if find(i) == find(j):
        print(1)
    else:
        print(0)