자바 코딩테스트 강좌, 다각형의 면적 구하기

안녕하세요! 이번 강좌에서는 다각형의 면적을 구하는 문제를 다루어 보겠습니다. 이 문제는 자바를 사용하여 구현할 것이며, 기초적인 수학 개념과 알고리즘을 적용하여 문제를 해결하는 과정을 자세히 설명하겠습니다.

문제 설명

주어진 점들의 좌표를 기반으로 다각형의 면적을 계산하는 프로그램을 작성하세요. 점들은 (x₁, y₁), (x₂, y₂), ..., (x_n, y_n) 형태로 주어지며, 이 점들을 연결하여 다각형을 구성한다고 가정합니다. 구하는 면적은 다음과 같은 조건을 충족해야 합니다:

점들은 시계 방향 또는 반시계 방향으로 주어집니다.
정확하고 효율적인 알고리즘을 작성해야 합니다.

입력

첫 번째 줄에는 점의 개수 n이 주어집니다. 다음 n개의 줄에는 각 점의 좌표 x, y가 정수로 주어집니다.

출력

다각형의 면적을 실수 형태로 출력하되, 소수점 이하 둘째 자리까지 반올림해야 합니다.

예제 입력

예제 출력

12.00

해결 방법

다각형의 면적을 구하는 방법으로는 다양한 알고리즘이 있지만, 이번 강좌에서는 슈뢰더의 공식(또는 다각형의 면적 공식)을 이용하겠습니다. 이 공식에 따르면, 다각형의 면적 A는 다음과 같이 계산됩니다:

A = 0.5 * |Σ (x_iy_i+1 - y_ix_i+1)|

여기서 (x_i, y_i)는 다각형의 각 점의 좌표이며, (x_n+1, y_n+1) = (x₁, y₁)와 같은 방식으로 처음 점으로 돌아갑니다.

1단계: 알고리즘 구조 설계

우선 프로그램의 기본 구조를 설계해 보겠습니다. 프로그램은 다음과 같은 4단계로 구성됩니다:

입력 받기
면적 계산하기
결과 출력하기
정리하기

2단계: 입력 받기

자바에서는 Scanner 클래스를 통해 사용자 입력을 받을 수 있습니다. 각 점의 좌표를 ArrayList를 사용하여 저장하겠습니다. 코드 예시는 다음과 같습니다:

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class PolygonArea {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 점의 개수
        List points = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            points.add(new Point(x, y));
        }
        scanner.close();
    }
    
    static class Point {
        int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

3단계: 면적 계산하기

이제 면적을 계산하는 메서드를 추가할 차례입니다. 면적 계산은 for문을 이용하여 각 점에 대해 위의 공식을 적용하면 됩니다:

public static double calculateArea(List points) {
    double area = 0.0;
    int n = points.size();

    for (int i = 0; i < n; i++) {
        Point p1 = points.get(i);
        Point p2 = points.get((i + 1) % n); // 다음 점, 마지막 점은 첫 번째 점을 연결
        area += p1.x * p2.y - p2.x * p1.y;
    }
    return Math.abs(area) / 2.0;
}

4단계: 결과 출력하기

이제 마지막으로 계산된 면적을 원하는 형식으로 출력하는 코드를 추가하겠습니다. 메인 메서드에 다음 코드를 추가해 줍니다:

double area = calculateArea(points);
System.out.printf("%.2f\n", area);

전체 코드

이제 모든 코드를 하나로 정리하면 다음과 같습니다:

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class PolygonArea {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 점의 개수
        List points = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            points.add(new Point(x, y));
        }
        scanner.close();
        
        double area = calculateArea(points);
        System.out.printf("%.2f\n", area);
    }

    static class Point {
        int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static double calculateArea(List points) {
        double area = 0.0;
        int n = points.size();

        for (int i = 0; i < n; i++) {
            Point p1 = points.get(i);
            Point p2 = points.get((i + 1) % n); // 다음 점, 마지막 점은 첫 번째 점을 연결
            area += p1.x * p2.y - p2.x * p1.y;
        }
        return Math.abs(area) / 2.0;
    }
}

정리

이번 강좌에서는 다각형의 면적을 구하는 문제를 풀어보았습니다. 우리 다룬 알고리즘은 슈뢰더의 공식을 바탕으로 하였으며, 이는 실제 프로그래밍 대회에서도 자주 사용됩니다. 각 단계마다 코드를 작성하며 알고리즘을 직접 구현해보는 경험이 매우 유익했을 것입니다.

이제 여러분도 이 알고리즘을 바탕으로 다양한 형태의 다각형에 대해 면적을 구하는 문제를 풀어볼 수 있습니다. 더 나아가 다른 아이디어와 알고리즘을 접목시켜 더욱 발전된 문제를 해결하는 데 도전해 보시기 바랍니다. 다음 강좌에서 더 많은 알고리즘 문제를 다르게 해보세요!