[Java] 점 사이의 거리

Minuuu·2023년 1월 16일

알고리즘

목록 보기

3/36

목적

처음 이 알고리즘을 접하는 사람이 쉽게 이해할 수 있도록 작성
두 점 사이의 거리를 구하는 알고리즘을 최대한 쉽게 설명(초보자 관점)
가지치기를 이용한 최적화 방법 소개

1. 문제 설명

n개의 점이 주어진다 그 중 가장 가까이 위치한 두 점을 찾아 두 거리를 출력한다

거리가 같은 점들의 갯수를 출력한다

2. 점 사이의 거리 알고리즘 소개

두점사이의 거리 구하기 공식

D(p1, p2) = \sqrt {(x_{p1} - x_{p2})^2 + (y_{p1} - y_{p2})}

두 점을 구하는 방법으로는 위와 같은 수학 공식을 이용한다
두 점의 x와 y를 각각 빼서 제곱한 값에 루트를 씌워주면 두 점 사이의 거리를 구할 수 있다
근데 이 때 이렇게 생각할 수 있다

D^2 = {(x_{p1} - x_{p2})^2 + (y_{p1} - y_{p2})}

이렇게 D^2를 먼저 구하고 마지막 계산할때만 제곱근을 씌워준다면
쉽게 거리계산을 구할 수 있다 그러니 거리의 제곱을 구하는 함수를 정의해 마지막에
제곱근을 넣어주는 방식으로 풀어보겠다.

A(-1, 5) B(2, 5) C(3, 2) D(3, 6) E(-1, 6)
위 그림을 보면 좌표는 점이라는 하나의 대상이 X좌표, Y좌표라는 두개의 데이터로 표현
하나의 대상이 여러 값을 가질 때 구조체와 클래스로 정의하는 것이 편리하다!!

class Point2D{
    int x;
    int y;
    public Point2D(int x, int y){
        this.x = x;
        this.y = y;
    }
}

우리는 위와 같이 클래스를 정의해서 적용할 것이다.

3. 가지치기 방법

두 데이터를 접근하려면 아래와 같이 반복문을 짜 모든 경우를 반복문으로 조회 가능하다

for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        //순회
    }
}

위와 같은 코드는 두개의 데이터 모두 접근 가능하나 효율적이지 않다
그 이유는
1) 일단 두 데이터를 비교할 때 자신을 포함하게 된다 (i == j) ex) (1, 1), (2, 2) (3, 3)....

2) 동일한 쌍을 2번 조회하는 경우가 생긴다(0, 1) = (1, 0) / (1, 2) = (2, 1)
=> 이런 경우는 제외하고 탐색하는 것이 효율적

이를 구분 하는 방법은 간단하다
작성한 반복문에서 3가지로 분류할 수 있다

i < j 인 경우
i = j 인 경우
i > j 인 경우
서로 다른 인덱스가 짝 지어지길 원한다면 i < j 거나 j > i 그룹들 중 하나만 조회
이를 코드로 옮기면

for(int i = 0; i < n; i++){
    for(int j = 0; j < i; j++){ // 변한 곳
        // <i, j> := (i < j) 인 모든 i, j 쌍을 순회
    }
}

자기와 자기자신을 나타내는 쌍도 나오지 않고, 서로 다른 쌍이 중복해서 나오지도 않는다

4. 최종 코드

이제 위의 소개한 내용을 적용시켜보면

// 2차원 평면 점사이의 거리 구하기 알고리즘
// 입력 형식
// 첫 줄에는 점의 수 N (2 <= N <= 1000)
// 그 후 N줄에 걸쳐 점의 좌표를 나타내는 두 정수가 주어진다(공백으로 구분) 모든 좌표는 절대값 1만이하, 좌표는 서로 다르다는 조건

import java.util.Scanner;

// 출력 형식
// 첫 줄에는 가장 가까운 두 점의 거리를 소수점 두번째 자리에서 반올림하여 첫번째 자리까지 출력
// 두 번째 줄에는 그 거리만큼 떨어진 점 쌍의 수를 출력
public class Q2F {
    public static final Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        int n = sc.nextInt(); // 점의 수
        Point2D[] points = new Point2D[n]; // 객체 배열 생성
        for(int i = 0; i < n; i++){
            int x = sc.nextInt(); // 점의 x좌표 입력
            int y = sc.nextInt(); // 점의 y좌표 입력
            points[i] = new Point2D(x, y); // 객체 배열 값 추가
        }

        int minDist = Integer.MAX_VALUE; // 가장 짧은 거리(초기화)
        int minCount = 0; // minDist만큼의 거리를 가진 점의 수
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){ // n = 2라면 1,0
                // 두 점의 제곱 계산 함수
                int sqd = points[i].getSquaredDistanceTo(points[j]);
                if(sqd < minDist){ // 가장 짧은 거리보다 작다면
                    minDist = sqd; // 최소 거리 갱신
                    minCount = 1; // minDist와 같은 거리의 점 갱신
                    // sqd라는 최소거리가 있기에 1로 갱신
                }else if(sqd == minDist){
                    // 갱신하지 않아도 최소거리를 가지면
                    minCount++;
                }
            }
        }
        System.out.printf("%.1f\n", Math.sqrt(minDist));
        System.out.printf("%d", minCount);
    }
}
class Point2D{
    int x;
    int y;
    public Point2D(int x, int y){
        this.x = x;
        this.y = y;
    }
    // 거리의 제곱을 구하는 함수
    public int getSquaredDistanceTo(Point2D target){
        int deltaX = this.x - target.x;
        int deltaY = this.y - target.y;
        return deltaX * deltaX + deltaY * deltaX;
    }
}

이렇게 class를 정의하고 객체배열을 이용해 풀 수 있다