[acmicpc/1004] 어린왕자 문제

public class Main {
    static class StarNode {
        public StarNode(int x, int y, int r) {
            this.x = x;
            this.y = y;
            this.r = r;
        }
        int value = 0, x = 0, y = 0, r = 0;
    }
    static Scanner sc = new Scanner(System.in);
    static StarNode s = null;
    static StarNode e = null;
    static StarNode[] stArr = null;
    static int count = 0, stNum = 0;
    public static void main(String[] args){
        int testCase = sc.nextInt();
        for(int i = 0 ; i < testCase; i++){
            s = new StarNode(sc.nextInt(), sc.nextInt(), 0);
            e = new StarNode(sc.nextInt(), sc.nextInt(), 0);
            stArr = new StarNode[sc.nextInt()];
            for(int j = 0 ;  j < stArr.length; j++)
                stArr[j] = new StarNode(sc.nextInt(), sc.nextInt(), sc.nextInt());
            for(int j = 0 ; j < stArr.length; j++){
                int sx = stArr[j].x - s.x , sy = stArr[j].y - s.y;
                int ex = stArr[j].x - e.x , ey = stArr[j].y - e.y;
                int r = stArr[j].r*stArr[j].r;
                if((sx*sx+sy*sy<r) ^ (ex*ex+ey*ey<r)) count++;
            }
            System.out.println(count);
            count = 0;
        }
    }
}
 

풀면서 깨닳은 점이 하나 있다.
 "다양한 방면으로 생각할 것"

 흔이 있는 DFS, BFS, Floyd 등의 알고리즘의 패턴을 기억해놔 풀이를 하곤 하는데, 이런 쉬운 문제를 풀면서 부끄러웠던 것이.

 일단 데이터를 시각화는 아니여도 트리형식으로 맵을 만들고 BFS방식으로 체크하여 탐색하려고 했으나 이런 방식으로 해도 정답은 되지만 문제에서 요구하는 요구사항만 만족하면 된다는 것을 뒤늦게 깨닳았다. (그리고 새벽에 부끄러워서 자신의 싸대기를 얼마나 날렸던지.)

 지금까지 내가 풀었던 방식은 DFS, BFS 문제인지를 먼저 확인하고 해당 문제가 가지고있는 많은 경우의 수들을 체크하였다. 그 후 몇가지 패턴을 확립하여 탐색 요소를 만들어 탐색하기 시작하는 것이 패턴이였는데 이런 쉬운문제는 그냥 몇가지 규칙을 체크했으면 되는 부분이였다. ( 다시한번 생각하지만 이 문제는 결코 어린왕자가 행성을 경로를 출력하라고 말하지도 않았고 몇가지 행성을 지나치면 되냐, 이것만 초점을 잡았기에 구지 맵을 만들 필요가 없다.)

 정리하자면 문제를 푸는 규칙은 "경우의 수 또는 문제에서 요구하는 패턴을 인식하고, 해당 패턴을 어떠한 알고리즘으로 풀지 선택하고 기반 지식을 찾아나가 풀어야한다." 

 이 문제에서 쓰인 것은

 x^2 + y^2 = r^2 인데 이는 원의 가장자리 선의 어떤 위치(x,y)라도 제곱하여 두항을 더하면 반지름(r)의 제곱과 같다.

 증명은, R(0,0)이고 반지름은 2일때 상하좌우 0,2 2,0 0,-2 -2,0 의 제곱하여 더한 후 r제곱(4)와 비교하면 모두같다.

 이용방법은 해당 행성의 r^2보다 크면 벗어난거이며 작으면 내부의 어떠한 점이라는 것을 알아낼 수 있다. 따라서 위와 같은 공식을 썻다.

 끝!