[ABC259] D - Circumferences (AtCoder Beginner Contest 259 in Java)

문제 : abc259_d

 

  내 경우엔 그래프로 변경해서 풀었다. 우선 ArrayList의 idx를 기준으로 0번에 s, 1번에 t를 둔다. 이후 N개의 원을 입력받으면서 s와 t를 포함해서 모든 원의 쌍들에 대해 서로 인접해 있다면 양방향 간선을 연결한다(코드의 edgeChk, O(3000^2)). 단, s와 t의 경우엔 외곽선에 겹칠 경우에만 겹친다고 판단하고 간선을 연결한다(코드의 circumferenceChk).

 

예를들어 이하의 입력을 보자.

4
0 -2 3 3
0 0 2
2 0 2
2 3 1
-3 3 3

이에 대한 이미지와 각 idx는 다음과 같다.

그리고 간선정보는 다음과 같다. (예를들어 1행 4열의 v는 idx 1과 idx 4가 인접함을 뜻한다.)

  그럼 이제 이 문제는 N+2개의 정점이 있는 그래프에 대해 간선이 이미 주어진 상태에서 단순히 bfs 혹은 dfs로 idx0에서 출발해 idx1에 도착할 수 있는지 확인하는 간단한 그래프 탐색 문제로 변경된다.

 

 

코드 :  github

...
class Circle {
    long x, y, r;
    public Circle(long x, long y, long r) {
        this.x = x;
        this.y = y;
        this.r = r;
    }
    public static boolean edgeChk(Circle a, Circle b) {
        if (a.r == 0) return circumferenceChk(a.x, a.y, b);
        if (b.r == 0) return circumferenceChk(b.x, b.y, a);
        long gapX = 1l*(a.x-b.x)*(a.x-b.x);
        long gapY = 1l*(a.y-b.y)*(a.y-b.y);
        if (gapX+gapY == 0) return false;
        if (gapX+gapY < 1l*(a.r-b.r)*(a.r-b.r)) return false;
        return 1l*(a.r+b.r)*(a.r+b.r) >= gapX+gapY;
    }
    private static boolean circumferenceChk(long x, long y, Circle a) {
        long gapX = (a.x-x)*(a.x-x);
        long gapY = (a.y-y)*(a.y-y);
        return 1l*a.r*a.r == gapX+gapY;
    }
}

private ArrayList<Integer>[] edges;
    private boolean[] v;
    private boolean dfs(int idx) {
        if (idx == 1) {
            return true;
        }
        for (int next : edges[idx]) {
            if (v[next]) continue;
            v[next] = true;
            if (dfs(next))
                return true;
        }
        return false;
    }
    private void solution() throws Exception {
        int n = nextInt();
        ArrayList<Circle> arr = new ArrayList<>();
        edges = new ArrayList[n+2];
        v = new boolean[n+2];
        for (int i = 0; i <= n+1; i++) edges[i] = new ArrayList<>();
        arr.add(new Circle(nextInt(), nextInt(), 0));
        arr.add(new Circle(nextInt(), nextInt(), 0));
        if (arr.get(0).x == arr.get(1).x && arr.get(0).y == arr.get(1).y) {
            System.out.println("Yes");
            return;
        }
        for (int i = 2; i <= n+1; i++) {
            Circle circle = new Circle(nextInt(), nextInt(), nextInt());
            arr.add(circle);
            for (int j = 0; j < i; j++) {
                if (Circle.edgeChk(circle, arr.get(j))) {
                    edges[i].add(j);
                    edges[j].add(i);
                }
            }
        }
        v[0] = true;
        System.out.println(dfs(0)?"Yes":"No");
    }
...