BOJ 14588 - Line Friends (Small)

문제

백준 온라인 저지 - 14588번

풀이 과정

선분의 겹칩 유무를 이용해서 각 선분간의 최소 거리 값을 구하는 문제입니다.

모든 선분간의 최소 거리 정보를 알아야하고 N 이 최대 300 이기 때문에 플로이드 와샬 알고리즘을 활용했습니다.
문제를 해결하고 선분 겹칩 연산과 관련해서 다른 분의 제출 코드를 확인해봤는데
다음과 같은 좋은 방법도 있는 것을 알게 되었습니다.

a1, b1 = 선분 1 양 끝점
a2, b2 = 선분 2 양 끝점
if max(a1, a2) <= min(b1, b2):
    # 두 선분 겹침

위 코드는 두 선분같의 끝 점을 이용해서 max, min 을 계산하고 이를 비교하여 겹침 유무를 판단하는 의사코드입니다.
이후에 이와 유사하게 선분 겹침 유무를 판단해야 할 때 이 방법을 사용해도 좋을 것 같습니다. 😄

코드

import sys

N = int(input())
lines = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
Q = int(input())
questions = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]


def check_overlap(pivot, opponent):
    if opponent[0] > pivot[1]:
        return False
    elif opponent[1] < pivot[0]:
        return False

    return True


def make_graph():
    dist = [[sys.maxsize] * N for _ in range(N)]

    for (p_idx, pivot) in enumerate(lines):
        for (o_idx, opponent) in enumerate(lines):
            if p_idx != o_idx and check_overlap(pivot, opponent):
                dist[p_idx][o_idx] = 1

    return dist


def floyd(dist):
    for v in range(N):
        dist[v][v] = 0

    for k in range(N):
        for u in range(N):
            for v in range(N):
                dist[u][v] = min(dist[u][v], dist[u][k] + dist[k][v])


def solution():
    dist = make_graph()
    floyd(dist)

    for frm, to in questions:
        cost = dist[frm - 1][to - 1]
        answer = cost if cost != sys.maxsize else -1
        print(answer)


solution()