백준 2477 참외밭 Java: 육각형 넓이를 신발끈 공식으로 구하기

백준 2477번 ‘참외밭’은 ㄱ자 모양 밭의 넓이에 1㎡당 참외 수를 곱하는 문제다. 가장 큰 직사각형에서 움푹 팬 직사각형을 빼도 되지만, 여섯 변을 순서대로 좌표로 바꾼 뒤 신발끈 공식을 적용하면 밭의 방향과 시작 위치를 따로 구분하지 않아도 된다.

• 백준 2477번 참외밭

방향과 길이를 좌표로 바꾸기

출발점을 (0, 0)으로 두고 입력된 여섯 변을 차례로 이동한다.

방향 번호	이동
1 동쪽	x += length
2 서쪽	x -= length
3 남쪽	y -= length
4 북쪽	y += length

입력은 밭의 경계를 한 방향으로 돌며 주어지므로 마지막 이동을 마치면 출발점으로 돌아온다. 이렇게 얻은 일곱 좌표 중 마지막 좌표는 첫 좌표와 같다.

신발끈 공식

꼭짓점이 순서대로 (x0, y0), (x1, y1), ...일 때 다각형 넓이의 두 배는 다음 절댓값이다.

|Σ (xi × y(i+1) - yi × x(i+1))|

이를 2로 나누면 ㄱ자 모양을 포함한 simple polygon의 넓이가 된다. 시계·반시계 방향에 따라 합의 부호만 달라지므로 마지막에 절댓값을 취한다.

Java 코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );

        int melonsPerSquareMeter = Integer.parseInt(reader.readLine());
        long[] x = new long[7];
        long[] y = new long[7];

        for (int edge = 0; edge < 6; edge++) {
            StringTokenizer tokenizer = new StringTokenizer(
                    reader.readLine()
            );
            int direction = Integer.parseInt(tokenizer.nextToken());
            int length = Integer.parseInt(tokenizer.nextToken());

            x[edge + 1] = x[edge];
            y[edge + 1] = y[edge];

            if (direction == 1) {
                x[edge + 1] += length;
            } else if (direction == 2) {
                x[edge + 1] -= length;
            } else if (direction == 3) {
                y[edge + 1] -= length;
            } else {
                y[edge + 1] += length;
            }
        }

        long twiceArea = 0;
        for (int vertex = 0; vertex < 6; vertex++) {
            twiceArea += x[vertex] * y[vertex + 1]
                    - y[vertex] * x[vertex + 1];
        }

        long area = Math.abs(twiceArea) / 2;
        System.out.println(area * melonsPerSquareMeter);
    }
}

좌표와 곱셈 결과를 long으로 두면 중간 곱에서 overflow를 걱정하지 않아도 된다. 이 문제의 변은 축과 평행하고 꼭짓점 좌표가 정수라 최종 넓이도 정수다.

큰 직사각형에서 작은 직사각형을 빼는 방법

원문은 가장 긴 가로·세로로 큰 직사각형을 구하고, 원형으로 이어진 방향 배열에서 움푹 팬 두 변을 찾아 작은 직사각형을 빼는 방식이었다.

field area = max width × max height
             - inner width × inner height

이 접근도 맞다. 다만 입력 시작점이 임의이고 여섯 변이 원형으로 이어져 있어 앞뒤 index를 보정하거나 modulo로 순환해야 한다. 특정 방향 pattern을 하드코딩하면 회전된 모양에서 빠뜨리기 쉽다. 신발끈 공식은 방향 code를 좌표 이동으로만 번역하면 되어 별도 notch pattern이 필요 없다.

당시 스터디에서 배운 지점

원문에는 움푹 팬 곳의 변은 앞뒤 변 방향이 같다는 방법과, 가장 긴 가로·세로 뒤쪽 index로 찾는 방법을 적었다. 두 번째 방법은 스터디원의 설명에서 배웠다고 남아 있다. 구현은 modulo 대신 앞뒤 칸을 복사해 hard coding했다.

이번 풀이에서는 그 “입력이 원형으로 이어진다”는 관찰을 좌표 polygon으로 확장했다. 공식 하나로 줄이는 것이 목적이라기보다, 회전 방향이나 시작 index에 흔들리지 않는 표현을 고른 것이다. 원의 포함 관계를 좌표로 옮기는 예시는 백준 1358 하키에서 비교할 수 있다.

복잡도와 검증 범위

변은 항상 6개이므로 시간과 추가 공간은 모두 O(1)이다. Java source를 수동 검토하고 네 방향으로 회전한 ㄱ자 polygon과 서로 다른 시작 vertex를 독립 rectangle-subtraction oracle과 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.