[백준/1004/실버3] 어린 왕자

https://www.acmicpc.net/problem/1004

1004번: 어린 왕자

 

<<풀이>>

일단 일차적인 풀이

예시 1번 같은 경우 맞췄다.. 하지만 전체적인 것은 오답이 났다.

 

 

원인

나는 왕자가 처음 있을 위치와 마지막에 있을 위치에 대해 단지 그 점에서의 원의 중심과의 거리를 구하고 만약에 원의 반지름 보다 작으면 원 안에 있다고 판단하여 거쳐야 하는 경계선 값을 증가시켜줬다.

 

근데, 잘생각해보면 이렇게 하면 논리적인 문제가 있는데, 만약 왕자의 도착 지점이 둘다 원 안에 있다면?? 이렇게 되면 오답이 나게 되는 것이다. 그러면 그 원의 경계선을 거치지 않기 때문이다.

 

 

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

class Main {

    static int answer;
    private int distance(String[] prince, String[] star) {
        int m = Integer.parseInt(prince[0]);
        int n = Integer.parseInt(prince[1]);

        int a = Integer.parseInt(star[0]);
        int b = Integer.parseInt(star[1]);

        return (int)Math.sqrt((m-a)*(m-a) + (n-b)*(n-b));
    }
    private void solution(String way, String arr) {
        String[] prince = way.split(" ");
        String[] star = arr.split(" ");

        if(prince[2].equals(star[0]) && prince[3].equals(star[1])) answer++;
        else if (distance(prince, star) < Integer.parseInt(star[2])) {
            answer++;
        }
    }

    public static void main (String[] args) throws Exception {
        ArrayList<Integer> list = new ArrayList<>();
       Main T = new Main();
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       int test = Integer.parseInt(br.readLine());
        for (int i = 0; i < test; i++) {
            String way = br.readLine();
            int n = Integer.parseInt(br.readLine());
            for (int j = 0; j < n; j++) {
                T.solution(way, br.readLine());
            }
            list.add(answer);
            answer = 0;
        }

        for (int x : list) System.out.println(x);


    }
}

 

 

 

<<해답>>

 

이 풀이는 ^(XOR) 연산자를 이용했다. 왕자의 첫 지점과 마지막 지점이 원 안에 있냐? 하나는 바깥에 하나는 안에 있냐 아니면 둘다 밖에 있냐?? 에 따라 나뉘는데, XOR연산자는 두 값이 달라야 1이 된다. 이 논리를 활용해서 하나는 바깥에 있고 하나는 안에 있을 때 true가 반환되어 경계선 지나가는 횟수를 1 증가 시킨다.

 

!!! 이렇게 푸니까 완벽,, 너무 어렵게 생각했다. 

 

다음에 이런 문제 나오면 이 논리로 제대로 활용해봐야겠다.

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int T = scanner.nextInt(); // 테스트 케이스의 개수

        for (int t = 0; t < T; t++) {
            int x1 = scanner.nextInt();
            int y1 = scanner.nextInt();
            int x2 = scanner.nextInt();
            int y2 = scanner.nextInt();

            int n = scanner.nextInt(); // 행성계의 개수

            int count = 0; // 행성계 진입/이탈 횟수

            for (int i = 0; i < n; i++) {
                int cx = scanner.nextInt(); // 행성계의 중점 x 좌표
                int cy = scanner.nextInt(); // 행성계의 중점 y 좌표
                int r = scanner.nextInt(); // 행성계의 반지름

                // 출발점과 도착점이 행성계 내부에 있을 경우, 둘 중 하나만 행성계 내부에 있는 경우
                boolean startInside = isInside(x1, y1, cx, cy, r);
                boolean endInside = isInside(x2, y2, cx, cy, r);

                // 출발점과 도착점이 행성계의 내부에 있는지 여부를 확인하여 행성계 진입/이탈 횟수를 증가시킴
                if (startInside ^ endInside) {
                    count++;
                }
            }

            System.out.println(count);
        }

        scanner.close();
    }

    // 점 (x, y)가 중심이 (cx, cy)이고 반지름이 r인 원 내부에 있는지 여부를 반환하는 메소드
    private static boolean isInside(int x, int y, int cx, int cy, int r) {
        int dx = x - cx;
        int dy = y - cy;
        return dx * dx + dy * dy < r * r;
    }
}