CCW(Counter Clock Wise, 백준 알고리즘 11758번)

♣ CCW

세 점 A, B, C가 존재할 때, 특정 선분에 대하여 특정 점이 왼쪽에 있는지(시계 방향) 오른쪽에 있는지(반시계 방향)를 판별할 수 있는 알고리즘이다. 아래 그림을 예로 들어보자. 

C -> B -> A로 진행하는데, 첫 번째 그림은 시계방향, 두 번째 그림은 직선, 세 번째 그림은 반시계 방향을 나타낸다. 

즉 선분 CB에 대한 점 A의 위치라고 생각하면 점 A는 선분 CB에 대해 각 그림에 따라 시계방향, 직선, 반시계 방향에 위치하는 것이다. 

 

CCW(Counter Clock Wise)는 이렇게 세 점을 이었을 때의 방향을 판단하는 데 유용하게 쓸 수 있는 알고리즘이다. 

신발끈 공식

 

점  A, B, C를 보면 선분 CB에 대한 점 A의 위치(방향)을 구하는 것이므로 점 C를 (x1, y1), 점 B를 (x2, y2), 점 A를 (x3, y3)라고 한다. 위의 신발끈 공식을 사용하여

 

x1*y2 + x2*y3 + x3*y1 - x2*y1 - x3*y2 - x1*y3 를 계산한다. 이를 함수로 만들면 아래와 같다. 

 

결과 ans이 0보다 크면 반시계 방향, 0이면 직선, 0보다 작으면 시계방향이다. 

 

♣ 백준 문제 이해하기

 

이 문제는 CCW를 사용하는 전형적인 문제이다. 점 P1, P2, P3가 있고, 선분 P1P2에 대한 점 P3의 위치(방향)을 구하면 된다. P3의 방향이 반시계 방향이면 1, 시계방향이면 -1, 일직선이면 0을 출력한다. 

 

 

♣ 코드

 

코드를 보면 ccw 함수를 이용해서 ans를 구해 방향을 판별한다. 방향(ans)가 0보다 크면 1, 0과 같으면 0, 0보다 크면 -1을 출력한다. 

 

ccw 알고리즘을 알면 쉽게 해결할 수 있는 문제였다. 왜 저 식이 성립하는지 아직 이해는 안 가지만... 원리에 대해서 좀 더 공부해야겠다. 

 

♣ 참고 자료

https://growth-coder.tistory.com/163#recentComments

[Algorithm][백준 11758][파이썬] CCW 알고리즘을 활용하여 선분의 교차 여부 판단

https://namu.wiki/w/%EC%99%B8%EC%A0%81

외적

https://zhocoding.tistory.com/121

백준 11758 CCW 파이썬