(BOJ25315 N수매화검법

• tags : (algorithm

  No matching post could be found

  - (CCW
• 문제 링크 : https://www.acmicpc.net/problem/25315
• 풀이 링크
  • Python

• 입력되는 선분의 선분 교차를 판별하는데, 몇가지 조건을 더 만족해야 한다.
• 첫 번째는 조건이라 하기에는 애매할 수 있지만, 최대 2500개 선분 입력을 처리해야 하고, 서로 교차하는지 확인하기 위해 $O(N^2)$의 시간이 필요하다.
• 두 번째는 가중치가 있고, 가중치를 활용한 연산 결과가 가장 작게 나오는 것을 목표로 한다.
• 이 외에는 특별한 내용이 없기 때문에 CCW를 활용하여 간단하게 해결할 수 있지만, 시간 조건 등과 같은 부분은 고민을 해 봐야 한다.

Point = tuple[int]


def get_ccw(A: Point, B: Point, C: Point) -> int:
    ccw = (B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1]) * (C[0] - A[0])
    return 0 if not ccw else 1 if ccw > 0 else -1


if __name__ == "__main__":
    N = int(input())
    actions = []
    for _ in range(N):
        sx, sy, ex, ey, w = map(int, input().split())
        actions.append(((sx, sy), (ex, ey), w))
    actions.sort(key=lambda x: x[2])
    ans = 0
    for idx, (S1, E1, w1) in enumerate(actions):
        count = 1
        for i in range(idx + 1, N):
            S2, E2, _ = actions[i]
            tmp1 = get_ccw(S1, E1, S2) * get_ccw(S1, E1, E2)
            tmp2 = get_ccw(S2, E2, S1) * get_ccw(S2, E2, E1)
            if tmp1 < 0 and tmp2 < 0:
                count += 1
        ans += count * w1
    print(ans)

• 코드가 길지 않기 때문에 전체 코드를 먼저 가져왔다.
• 우선 CCW 계산을 위한 함수를 만들었다.
• 입력은 list confrehension으로 처리할 수 있지만, 각 점을 더 편하게 가져다 쓰기 위해 tuple 형태로 저장했다.
  • 입력은 가중치 오름차순으로 정렬했는데, 이는 결과값을 최소로 만들기 위해서다.
• 2개의 for문의 구성이 독특하다고 생각할 수 있는데, 이는 시간을 최소화하기 위해 구성한 부분이다.
  • 성능과 관련해서는 뒷 부분에서 다시 한 번 다루겠다.
  • 비교를 위한 하나의 선분을 선택하고, 다른 선분과의 교차여부를 판별한다.
  • 이 때, 문제에서 어느 세 점도 한 직선에 있지 않다는 조건이 있기 때문에, CCW값만 비교하여 교차 여부를 판별할 수 있다.

for i in range(N):
    S1, E1, w1 = actions[i]
    count = 1
    for j in range(i + 1, N):
        S2, E2, w2 = actions[j]

for idx, (S1, E1, w1) in enumerate(actions):
    count = 1
    for _, (S2, E2, _) in enumerate(actions[idx + 1 :]):

• for문을 위의 두가지 방식으로도 구성해 보았다.
  • 우선 첫 번째 경우는 인덱스만 순회하고, 각 값을 가져오는 방식이고,
  • 두 번째는 enumerate만 사용하는 경우인데, if 조건문 대신 슬라이싱을 사용한 경우이다.
• 우선 성능은 가장 위에 작성된 코드, 인덱스만 순회하는 for문, enumerate만 사용하는 for문 순서이다.
  • enumerate가 일반적인 경우보다는 빠르지만, 슬라이싱이 포함되어 더 느리게 동작한것으로 보인다.