[ 14588 ] [ Floyd ] Line Friends (Small)

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

14588번: Line Friends (Small)

---

풀이 과정

---

1. 선분을 이용하여 그래프를 구성한다.

   • 두 선분이 친구 관계라면 1, 친구 관계까 아니라면 아주 큰 값(INT_MAX)으로 설정
   • 두 선분이 친구 관계인지 확인하려면 총 세가지 케이스를 확인해야 한다.
     1. 하나의 선분의 왼쪽 끝이 다른 선분 안에 있거나, (왼쪽은 겹치고 오른쪽은 선분 밖에)
     2. 오른쪽 끝이 다른 선분 안에 있거나. (오른쪽은 겹치고 왼쪽은 선분 밖에)
     3. 하나의 선분의 왼쪽 끝이 다른 선분보다 작고, 오른쪽 끝이 다른 선분보다 클 때(덮을 때)
     4. 아예 안에 들어있을 때는 (1), (2)에 걸리므로 따로 처리할 필요 없음

2. Floyd 알고리즘을 사용하여 각 선분에서 다른 선분으로 이동 가능한 최단 거리를 테이블로 미리 구성해 둔다.

   • 삼중 반복문을 통해 거쳐가는 모든 케이스 조사
   • 반복문 순서가 중요함!! 맨 바깥쪽 반복문이 거쳐가는 노드
     • distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
     • k가 거쳐가는 노드
   • T의 최대가 300이라서.. 300 * 300 * 300을 해야되는데 좀 크지 않나라고 생각했지만 잘 된다. 생각해보니 후에 Q개의 줄에 걸쳐 최단경로를 입력받고 출력해야되서 좀 오래걸리더라도 다 구해둬야 되는게 맞음.

3. 입력받은 두 선분 사이의 거리를 출력해 준다.

---

소스 코드

---

import sys

input = lambda : sys.stdin.readline().rstrip()

T = int(input())
lines = [list(map(int, input().split())) for _ in range(T)]
INT_MAX = int(10e9)
graph = [[INT_MAX] * T for _ in range(T)]

for i in range(len(lines)):
    for j in range(i+1, len(lines)):
        if (lines[i][0] <= lines[j][0] and lines[j][0] <= lines[i][1]) or \
        (lines[i][0] <= lines[j][1] and lines[j][1] <= lines[i][1]) or \
        (lines[j][0] <= lines[i][0] and lines[j][1] >= lines[i][1]):
            graph[i][j] = 1
            graph[j][i] = 1

for i in range(T):
    for j in range(T):
        for k in range(T):
            graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])

Q = int(input())
for _ in range(Q):
    src, dest = map(int, input().split())
    src, dest = src - 1, dest - 1

    if graph[src][dest] == INT_MAX:
        print(-1)
    else:
        print(graph[src][dest])