[코드트리/NOVICE MID] 가장 가까운 두 점 사이의 거리 (JAVA)

🔺 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
class Point {
    int x, y;
 
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        int N = Integer.parseInt(br.readLine());
        Point[] points = new Point[N];
 
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
 
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
 
            points[i] = new Point(x, y);
        }
 
        int diff = Integer.MAX_VALUE;
        for(int i = 0 ; i < N - 1 ; i++) {    // 모든 쌍에 대해 조사
            for(int j = i + 1 ; j < N ; j++) {
                int tmp = getDist(points[i], points[j]);
                diff = Math.min(diff, tmp);    // 최솟값 갱신
            }
        }
 
        System.out.println(diff);
    }
 
    // 두 점 사이 거리 반환 메소드
    public static int getDist(Point a, Point b) {
        return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
    }
}

 

 

 

 

🧩  해결 아이디어

• 완전 탐색 (물체 단위)

- 모든 쌍에 대해 전부 거리를 조사하여 그 중 제곱의 최솟값을 구한다.

- 시간 복잡도 : O(N^2)

 

 

 

---

🔺 다른 풀이들

- 점을 클래스로 받지 않고, 배열 2개를 만들어 x좌표와 y좌표 값을 저장했다.

import java.util.Scanner;
 
public class Main {
    public static final int INT_MAX = Integer.MAX_VALUE;
    public static final int MAX_N = 100;
 
    public static int n;
    public static int[] x = new int[MAX_N];
    public static int[] y = new int[MAX_N];
    
    // 두 점 사이의 거리의 제곱 값 반환
    public static int dist(int i, int j) {
        return (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        n = sc.nextInt();
 
        for(int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
        }
 
        // 모든 쌍에 대해서 거리 제곱값을 계산해 그 중 최솟값 탐색
        int minDist = INT_MAX;
 
        for(int i = 0; i < n; i++)
            for(int j = i + 1; j < n; j++)
                minDist = Math.min(minDist, dist(i, j));
        
        System.out.println(minDist);
    }
}

 

 

- 분할 정복도 가능하다구....

[백준] 2261번 : 가장 가까운 두 점 - JAVA [자바]

---

💬 느낀 점

간단한 문제를 너무 오래 고민해버렸다는ㄴ......

뇌가 진짜 이상하다...

일찍 자야겠다....

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 백준 2261번과 유사하다 함!

[백준] 2261번 : 가장 가까운 두 점 - JAVA [자바]