백준 11758번 - CCW 자바 풀이

문제 링크

문제 풀이 시간 : 1시간

문제 설명

3 점 P1, P2, P3가 주어진다.
P1, P2, P3를 순서대로 이은 선분이 반시계 방향을 나타내면 1
시계방향이면 -1
일직선이면 0 을 출력한다.

문제 풀이

처음에는 이 문제를 보고 기울기를 활용해서 푸는거 아닌가?

라는 생각으로 접근했다.

첫번째 선분의 기울기보다 두번째 선분의 기울기가 더 작으면 시계방향,

아니라면 반시계 방향으로 생각을하고 코드를 짰다.

초기 코드

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static class Point {
        private final int a;
        private final int b;

        Point(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }

    public static Point[] arr =new Point[3];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for (int i = 0; i < 3; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        int a = (arr[1].b - arr[0].b) / (arr[1].a - arr[0].a);
        int b = (arr[2].b - arr[1].b) / (arr[2].a - arr[1].a);

        if (a > b) {
            System.out.println(-1);
        } else if (a < b) {
            System.out.println(1);
        }
        else
            System.out.println(0);

    }
}

근데 틀렸다.

너무 단순하게 생각했던 것 같다.

조금만 더 생각을 해보면 이 문제는 단순히 기울기로는 풀 수 없는 문제인 것이다.

도저히 모르겠어서 문제의 제목인 CCW를 검색해 보았다.

CCW는 Counter-ClockWise 의 줄임말이다.

이 알고리즘은 평면상의 3개의 점의 위치관계를 판단하는 알고리즘이다.

일직선

반시계 방향

위와 같이 3가지 경우를 판단할 때 쓰이는 알고리즘이다.

식을 설명하자면

세 점 \text{A}(X_1, Y_1), \text{B}(X_2, Y_2), \text{C}(X_3, Y_3)이 있다고 가정했을 때,

\text{CCW} = (X_1 \cdot Y_2 + X_2 \cdot Y_3 + X_3 \cdot Y_1) - (X_2 \cdot Y_1 + X_3 \cdot Y_2 + X_1 \cdot Y_3)

이렇게 된다.

이 식이 나오게 된 방법은 문제를 풀 때 크게 중요하지 않은 부분이기 때문에 넘어가도록 하겠다.

위 식을 이해하기 쉽게 그림으로 나타낸다면 아래와 같다.

여기서 검은 선은 곱하고 더하기, 붉은 선은 곱하고 빼주면 된다.

이렇게 나온 결과가 0보다 작다면 시계방향, 0과 같다면 일직선, 0보다 크다면 반시계 방향을 나타내게 된다.

이 알고리즘을 활용해서 문제를 풀어보면 아주 쉽게 풀 수 있다.

정답 코드

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static class Point {
        private final int a, b;

        Point(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Point[] arr =new Point[4];
        for (int i = 0; i < 3; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        arr[3] = arr[0];
        int d = 0;
        for (int i = 0; i < 3; i++) {
            d += arr[i].a * arr[i + 1].b;
        }
        for (int i = 1; i <= 3; i++) {
            d -= arr[i].a * arr[i - 1].b;
        }

        if (d < 0) {
            System.out.println(-1);
        } else if (d > 0) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }
}

11758번 - CCW

문제 풀이 시간 : 1시간

문제 설명

문제 풀이

초기 코드

정답 코드

함께 읽으면 좋은 글

5430번 - AC

1966번 - 프린터 큐

1158 - 요세푸스 문제

2164번 - 카드2