백준 1004번 : 어린 왕자 자바

 

 

 

🧫 문제 분석

 

✔️ 출처

어린 왕자 실버 3

 

📖 문제

 

두 점 사이의 거리 공식을 이용하면 쉽게 풀리는 문제이다.

 

노션에서 직접 만듦

행성 경계의 좌표와 시작, 끝 지점의 좌표사이의 거리를 구하고

그 거리가 행성 경계의 반지름 보다 짧다면 이는 그 행성 안에 시작점이나 끝 지점이 있다는 뜻이고

이는 1번 진입/이탈을 해야한다는 의미이다. 

 

중요한 점은 시작 점과 끝점 둘 다 한 행성 안에 있을 수 있다. 이때는 진입/이탈이 없다.

따라서 시작 점이 행성 경계 안에 있는 경우 와 끝점이 행성 경계 안에 있는 경우만 따지면 된다.

---

🔅 문제 풀이

import java.io.*;
import java.util.*;

public class Main {

    static class Planet {
        int x,y, r;

        public Planet(int x, int y, int cost) {
            this.x = x;
            this.y = y;
            this.r = cost;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            Planet start = new Planet(Integer.parseInt(st.nextToken()), 
            				Integer.parseInt(st.nextToken()), 0);
            Planet end = new Planet(Integer.parseInt(st.nextToken()), 
            				Integer.parseInt(st.nextToken()), 0);

            int n = Integer.parseInt(br.readLine());
            Planet[] arr = new Planet[n];


            // 행성 배열 초기화
            for (int j = 0; j < n; j++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                int r = Integer.parseInt(st.nextToken());
                arr[j] = new Planet(x,y,r);
            }

            // 진입/이탈 횟수 카운팅
            int count = 0;
            for (Planet planet : arr) {
                double startR = getDistance(planet, start);
                double endR = getDistance(planet, end);

                // 두 점사이의 거리가 행성의 반지름 보다 작다면 진입 혹은 이탈했다고 본다.
                if ((planet.r > startR && planet.r <= endR) ||
                        (planet.r <= startR && planet.r > endR)) {
                    count++;
                }
            }
            sb.append(count).append("\n");
        }


        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static double getDistance(Planet planet, Planet dest) {
        return Math.sqrt(Math.pow(dest.x - planet.x, 2) + Math.pow(dest.y - planet.y, 2));
    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1.  항상 반례가 약하다. 알고리즘 테스트 케이스 기준을 잡아서 연습해야겠다.