백준 2389번 세상의 중심에서... JAVA 구현해보기

---

```

백준 2389번 세상의 중심에서... JAVA 구현해보기

```

이번 글을 통해 배워갈 내용

1.  백준 2389번 풀이

---

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

2389번: 세상의 중심에서...

 

 

백준 2389번 세상의 중심에서는

난이도 플래티넘 등급의 문제로서

 

관객의 수 N과 관객의 2차원 (X, Y) 좌표가 주어질 때

 

주어진 관객 N 명을 포함하는 원의 중앙 좌표값과 해당되는 반지름의 최소 값을 구해주면 되는 문제입니다.

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

 

먼저 입력을 받습니다

// 사람이 서있는 좌표 리스트
List<Point2D.Double> pplCoordinates = new ArrayList<>();

// 사람의 수
final int pplSize = Integer.parseInt(br.readLine());

// pplCoordinates 좌표값 입력
for (int i = 0; i < pplSize; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    final double x = Double.parseDouble(st.nextToken());
    final double y = Double.parseDouble(st.nextToken());
    Point2D.Double pt = new Point2D.Double(x, y);
    pplCoordinates.add(pt);
}

 

평균값을 구해줍니다

// 평균 값
double xPos = pplCoordinates.stream().map(pt -> pt.x).reduce(0.0, Double::sum) / pplSize;
double yPos = pplCoordinates.stream().map(pt -> pt.y).reduce(0.0, Double::sum) / pplSize;

 

이 부분이 핵심 알고리즘입니다.

경사 하강법(傾斜下降法, Gradient descent)을 이용한 풀이이며

경사 하강법에 대해서 궁금하신 분들은 아래 링크를 참조해주시기 바랍니다.

https://towardsdatascience.com/gradient-descent-algorithm-a-deep-dive-cf04e8115f21

Gradient Descent Algorithm — a deep dive

https://en.wikipedia.org/wiki/Gradient_descent

Gradient descent - Wikipedia

 

 

아래와 같이 (평균값 xy로 구한) 빨간 점이 있고

주황점 7개가 있다고 가정하면

Gradient Descent 알고리즘 설명자료 1

빗변의 길이 제곱

= (비교할 점 A의 x 값 - 현재 빨간 점의 x 값)에 제곱 +  (비교할점 A의 y 값 - 현재 빨간 점의 y 값)에 제곱)입니다

 

빗변 길이의 제곱 값을 비교해주면 빗변 크기를 비교하는 것과 같기 때문에

빗변 길이의 제곱을 비교합니다.

 

위 그림에서 d0을 기준으로 빗변을 잡고 있는 경우

d6가 더 크기 때문에 기준점을 d6에 연결된 점으로 바꿔줍니다.

그리고  빨간 점을 보정해줍니다.

그리고 보정해줄 때마다 정밀도를 곱해주는데 이 값을 조금씩 줄여주면 됩니다.

그리고 해당 작업을 반복해주면 답이 나옵니다.

 

Gradient Descent 알고리즘 설명자료 2

 

        // 보정값
        double precision = 0.1;
        // 반지름의 제곱
        double distance = 0;
        // 반복횟수는 다다익선
        for (int i = 0; i < 25000; i++) {
            int idx = 0;
            distance = findHypotenuse(xPos - pplCoordinates.get(0).x, yPos - pplCoordinates.get(0).y);
            for (int j = 1; j < pplSize; j++) {
                final double possibleDistance = findHypotenuse(xPos - pplCoordinates.get(j).x, yPos - pplCoordinates.get(j).y);
                // 길이 비교를 해서 클경우 새로운 빗변으로 변경
                // 보정할때 비교할 좌표 변경
                if (distance < possibleDistance) {
                    distance = possibleDistance;
                    idx = j;
                }
            }
            // 길이보정해주기
            xPos += (pplCoordinates.get(idx).x - xPos) * precision;
            yPos += (pplCoordinates.get(idx).y - yPos) * precision;
            precision *= 0.999;
        }

 

 

전체 코드는 아래와 같습니다.

 

package com.bj;

import java.awt.geom.Point2D;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {

        // 사람이 서있는 좌표 리스트
        List<Point2D.Double> pplCoordinates = new ArrayList<>();

        // 사람의 수
        final int pplSize = Integer.parseInt(br.readLine());

        // pplCoordinates 좌표값 입력
        for (int i = 0; i < pplSize; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            final double x = Double.parseDouble(st.nextToken());
            final double y = Double.parseDouble(st.nextToken());
            Point2D.Double pt = new Point2D.Double(x, y);
            pplCoordinates.add(pt);
        }

        // 평균 값
        double xPos = pplCoordinates.stream().map(pt -> pt.x).reduce(0.0, Double::sum) / pplSize;
        double yPos = pplCoordinates.stream().map(pt -> pt.y).reduce(0.0, Double::sum) / pplSize;

        // 보정값
        double precision = 0.1;
        // 반지름의 제곱
        double distance = 0;
        // 반복횟수는 다다익선
        for (int i = 0; i < 25000; i++) {
            int idx = 0;
            distance = findHypotenuse(xPos - pplCoordinates.get(0).x, yPos - pplCoordinates.get(0).y);
            for (int j = 1; j < pplSize; j++) {
                final double possibleDistance = findHypotenuse(xPos - pplCoordinates.get(j).x, yPos - pplCoordinates.get(j).y);
                // 길이 비교를 해서 클경우 새로운 빗변으로 변경
                // 보정할때 비교할 좌표 변경
                if (distance < possibleDistance) {
                    distance = possibleDistance;
                    idx = j;
                }
            }
            // 길이보정해주기
            xPos += (pplCoordinates.get(idx).x - xPos) * precision;
            yPos += (pplCoordinates.get(idx).y - yPos) * precision;
            precision *= 0.999;
        }

        distance = Math.sqrt(distance);

        System.out.print(xPos + " " + yPos + " " + distance);
    }

    // 빗변 구하기
    static double findHypotenuse(double rhs, double lhs) {
        return (rhs * rhs) + (lhs * lhs);
    }
}

//codemasterkimc.tistory.com [김씨의 코딩 스토리]

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

비슷한 문제

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

2626번: 헬기착륙장

 

---

참조

https://en.wikipedia.org/wiki/Gradient_descent

Gradient descent - Wikipedia

https://ideone.com/vju6Uh

Ideone.com

https://www.baeldung.com/java-gradient-descent