[25558] 네비게이션

이 문제는 입력받은 각 좌표간의 거리를 계산해서 가장 짧은 거리의 좌표값을 입력한 번호를 찾으면 되는 문제다.

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main() {
    int n = 0;

    long start_x;
    long start_y;
    long end_x;
    long end_y;

    std::cin >> n;

    std::vector<long> results;

    std::cin >> start_x >> start_y >> end_x >> end_y;

    for(int i=0; i<n; ++i) {

        int m = 0;

        long prev_x = start_x;
        long prev_y = start_y;

        long total_dist = 0;

        std::cin >> m;

        for(int j=0; j<m; ++j) {
            long point_x;
            long point_y;

            std::cin >> point_x >> point_y;

            long dist = std::abs(point_x - prev_x) + std::abs(point_y - prev_y);

            total_dist+=dist;

            prev_x = point_x;
            prev_y= point_y;
        }

        long dist = std::abs(end_x - prev_x) + std::abs(end_y - prev_y);

        total_dist+=dist;
        results.push_back(total_dist);
    }

    auto it = std::min_element(results.begin(), results.end());
    long index = std::distance(results.begin(), it);

    std::cout << index + 1 << std::endl;

    return 0;
}

 

코드는 길지만 복잡하지는 않다.

 

맨 처음 입력받은 좌표를 저장하고 반복문으로 좌표를 받으면서 이전에 받은 좌표와 거리를 계산해서 결과 벡터에 넣고 벡터에서 최솟값의 index를 출력하면 된다.

 

간단한 문제이지만 standard library에 있는 함수들을 많이 사용한 것을 볼 수 있다.

 

- std::abs() : 절댓값을 return 해주는 함수이다.

- std::min_element() : vector에서 최솟값의 iterator를 return 해주는 함수이다. (최댓값을 받고 싶으면 max_element()를 사용하면 된다)

- std::distance() : 두 iterator 사이의 거리를 반환해주는 함수이다.

 

이 문제를 처음 제출했을 때 실패가 떴는데 그 이유는 내가 정수 변수들을 int로 선언했었는데, 입력값의 범위가 int 범위를 초과했기 때문이였다. 그래서 범위가 더 긴 long으로 수정해서 다시 제출해서 통과했다.