백준 1004 어린 왕자 Java: 원 내부 여부를 XOR로 비교하기

백준 1004번 ‘어린 왕자’는 출발점에서 도착점으로 갈 때 반드시 통과해야 하는 행성계 경계의 최소 횟수를 구한다. 각 행성계를 원으로 보면 출발점과 도착점 중 정확히 한 점만 원 안에 있을 때 그 원의 경계를 한 번 통과한다.

• 백준 1004번 어린 왕자

왜 XOR 조건인가

한 원에 대해 네 경우를 나눌 수 있다.

출발점	도착점	경계 통과 여부
밖	밖	통과하지 않음
안	안	통과하지 않음
안	밖	한 번 통과
밖	안	한 번 통과

두 boolean 값이 다를 때만 참인 XOR가 이 표와 정확히 같다.

inside(start) XOR inside(destination)

문제에서는 행성계가 서로 만나거나 겹치지 않고 출발점과 도착점이 경계 위에 있지 않다고 보장한다. 따라서 각 원에 대해 안과 밖만 판단해 횟수를 더하면 된다.

원 내부 판정

원의 중심이 (cx, cy), 반지름이 r, 점이 (px, py)라면 다음 조건으로 내부를 확인한다.

(px - cx)² + (py - cy)² < r²

square root를 구할 필요가 없고, Math.pow()로 부동소수점 연산을 할 이유도 없다. 좌표 차를 long으로 만든 뒤 곱한다.

Java 코드

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

public class Main {
    private static boolean isInside(
            int pointX,
            int pointY,
            int centerX,
            int centerY,
            int radius
    ) {
        long dx = (long) pointX - centerX;
        long dy = (long) pointY - centerY;
        return dx * dx + dy * dy < (long) radius * radius;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        int testCount = Integer.parseInt(reader.readLine());
        StringBuilder output = new StringBuilder();

        for (int test = 0; test < testCount; test++) {
            StringTokenizer tokenizer = new StringTokenizer(
                    reader.readLine()
            );
            int startX = Integer.parseInt(tokenizer.nextToken());
            int startY = Integer.parseInt(tokenizer.nextToken());
            int endX = Integer.parseInt(tokenizer.nextToken());
            int endY = Integer.parseInt(tokenizer.nextToken());

            int planetCount = Integer.parseInt(reader.readLine());
            int crossingCount = 0;

            for (int planet = 0; planet < planetCount; planet++) {
                tokenizer = new StringTokenizer(reader.readLine());
                int centerX = Integer.parseInt(tokenizer.nextToken());
                int centerY = Integer.parseInt(tokenizer.nextToken());
                int radius = Integer.parseInt(tokenizer.nextToken());

                boolean startInside = isInside(
                        startX, startY, centerX, centerY, radius
                );
                boolean endInside = isInside(
                        endX, endY, centerX, centerY, radius
                );

                if (startInside != endInside) {
                    crossingCount++;
                }
            }

            output.append(crossingCount).append('\n');
        }

        System.out.print(output);
    }
}

원문은 두 방향을 별도 if로 작성했다. startInside != endInside로 바꾸면 “정확히 한 점만 내부”라는 문제 조건이 code에 그대로 드러난다.

복잡도와 자주 틀리는 부분

test case별 행성계 수를 N이라고 하면 모든 원을 한 번씩 확인하므로 시간 복잡도는 O(N), 추가 공간은 O(1)이다.

• 두 점이 모두 같은 원 안에 있으면 그 원의 경계는 통과할 필요가 없다.
• 두 점이 모두 밖이어도 그 원을 일부러 통과하는 경로는 최소 경로가 아니다.
• 문제 보장상 점이 원 위에 없으므로 내부 비교는 <다.
• 좌표 차를 먼저 long으로 바꾸지 않으면 제곱 전에 int overflow가 날 수 있다.

예상보다 순순히 통과했던 문제

원문에는 그림을 보고 “이게 되나?” 싶었지만 첫 예제가 맞아 바로 제출했고, 생각보다 순순히 통과해 신기했다고 적혀 있다. 출발점이 속한 원의 수와 도착점이 속한 원의 수를 처음에는 더하려 했고, 곧 두 점이 같은 원 안에 있으면 세면 안 된다는 조건을 발견했다.

그 차이를 지금의 언어로 정리하면 XOR다. 도형을 code로 옮길 때 경우의 수 표를 먼저 쓰면 두 개의 긴 조건문을 하나의 boolean 관계로 줄일 수 있다. 직사각형과 원의 합집합을 다루는 문제는 백준 1358 하키에서 이어진다.

검증 범위

Java source를 수동 검토하고 두 점 모두 밖·모두 안·출발점만 안·도착점만 안인 네 경우와 작은 random circle set을 독립 squared-distance oracle과 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.