[백준/BOJ] 17371번 : 이사 (그리디 알고리즘, 기하학)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 17371번 : '이사' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Gold I에 해당하며, 문제를 풀이하기 위해 그리디 알고리즘과 기하학에 대한 기초적인 이해가 필요합니다.

 

 

17371번 : 이사

 

N개의 편의시설에 대한 좌표가 주어졌을 때, 가장 가까운 편의시설과 가장 먼 편의시설까지의 거리의 평균이 최소가 되는 좌표를 구하는 문제입니다.

가능한 좌표가 여러 가지일 수 있으므로, 그들 중 하나의 답을 출력하면 정답으로 인정될 수 있습니다.

 

 

 

이해를 돕기 위해 간단히 그림을 그려 설명해보면, 여러 개의 편의시설 중 가장 먼 편의시설의 거리가 최소인 편의시설의 위치를 집의 위치로 잡으면, 가장 가까운 거리가 자동적으로 0이 되고 가장 먼 거리는 아까 최소로 잡았다고 했으므로 정답 중 하나인 위치가 됩니다.

따라서 O(N^2)으로 모든 집의 위치 관계를 비교해보면서 답을 얻어내면 됩니다.

 

 

#include <bits/stdc++.h>
using namespace std;

struct Point { int x, y; };

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;
    vector<Point> point(N);

    for(int i=0; i<N; i++)
        cin >> point[i].x >> point[i].y;

    int ans, minDist = INT_MAX;
    for(int i=0; i<N; i++) {
        double maxDist = 0;
        for(int j=0; j<N; j++) {
            double dist = sqrt(pow(point[i].x - point[j].x, 2) + pow(point[i].y - point[j].y, 2));
            maxDist = max(maxDist, dist);
        }
        if(maxDist < minDist) {
            minDist = maxDist;
            ans = i;
        }
    }
    cout << point[ans].x << " " << point[ans].y << "\n";
}

 

위의 그림을 풀이 코드로 나타내면 위와 같이 작성해볼 수 있습니다.

pair나 배열을 쓸까 고민했는데 코드의 가독성을 위해 Point 구조체를 사용하였습니다.

 

 

 

풀이 코드를 제출하면 위와 같은 기록으로 정답 처리를 받을 수 있습니다.