[BOJ 16491] 대피소 찾기

문제

---

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

풀이

---

로봇과 대피소의 수가 10 이하로 동일하게 주어진다.

각 로봇에 대피소를 하나씩 할당해 줘야 하는데, 동선이 겹치면 안 된다.

문제에는 로봇들이 서로 충돌하지 않게 대피소를 할당해 주라고 돼있는데, 이는 동선이 겹치지 않는 것보다 약한 조건이 아닌가 싶다.

동선이 겹쳐도 같은 시각에 다른 위치에 있으면 충돌하지 않으니 말이다.

다만 AC를 받는 것으로 보아 그런 데이터는 없는 듯하다.

브루트포스 풀이의 시간 복잡도는 O(N ** 2 * N!)이고, N = 10일 때도 TLE가 나지 않는다.

나는 백트래킹으로 풀었다.

코드

---

import sys

n = int(sys.stdin.readline())
robot = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
shelter = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]


def isintersect(x1, y1, x2, y2, x3, y3, x4, y4):
    p = (x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1)
    q = (x3 - x1) * (y4 - y3) - (x4 - x3) * (y3 - y1)
    r = (x3 - x1) * (y2 - y1) - (x2 - x1) * (y3 - y1)
    if p:
        return (p * q >= 0) and (abs(p) >= abs(q)) and (p * r >= 0) and (abs(p) >= abs(r))
    else:
        s = (x3 - x1) / (x2 - x1) if y1 == y2 else (y3 - y1) / (y2 - y1)
        t = (x4 - x1) / (x2 - x1) if y1 == y2 else (y4 - y1) / (y2 - y1)
        return q == 0 and r == 0 and (s <= 1 or t <= 1) and (s >= 0 or t >= 0)


queue = [[i] for i in range(n)]
while queue:
    tar = queue.pop()
    length = len(tar)
    if length == n:
        for i in range(n):
            print(tar[i] + 1)
        break

    x3, y3 = robot[length]
    for j in range(n):
        if j not in tar:
            x4, y4 = shelter[j]
            for i in range(length):
                x1, y1 = robot[i]
                x2, y2 = shelter[tar[i]]
                if isintersect(x1, y1, x2, y2, x3, y3, x4, y4):
                    break
            else:
                queue.append(tar + [j])