백준 1393번 [음하철도 구구팔](C++) -yes6686- 티스토리

백준 문제 풀이: 1393 (음하철도 구구팔)

---

문제 링크: https://www.acmicpc.net/problem/1393

문제 설명:

현재 위치(xs, ys)에 있는 사람이 직선 경로를 따라 이동하는 음하철도의 가장 가까운 지점을 찾아야 합니다. 음하철도는 (xe, ye)에서 시작하여 방향 벡터(dx, dy)에 따라 이동하며, 음하철도는 무한히 계속됩니다. 최단 거리를 가지는 지점의 좌표를 구하는 문제입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

// 두 수의 최대공약수 계산
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// 두 점 (a, b)와 (c, d) 사이의 거리의 제곱 계산
int dis(int a, int b, int c, int d) {
    return ((a - c) * (a - c) + (b - d) * (b - d));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int xs, ys; // 사람의 위치
    cin >> xs >> ys;

    int xe, ye, dx, dy; // 음하철도의 시작 좌표와 방향 벡터
    cin >> xe >> ye >> dx >> dy;

    // 방향 벡터를 단위 벡터로 변환
    int m = gcd(dx, dy);
    dx /= m;
    dy /= m;

    // 최단 거리 계산 초기화
    int minV = dis(xs, ys, xe, ye); // 초기 거리
    int ansX = xe, ansY = ye; // 초기 좌표 설정

    while (true) {
        // 다음 음하철도 위치로 이동
        xe += dx;
        ye += dy;

        // 새로운 거리 계산
        int currentDistance = dis(xs, ys, xe, ye);
        
        // 거리가 줄어들면 갱신
        if (minV > currentDistance) {
            minV = currentDistance;
            ansX = xe;
            ansY = ye;
        } 
        // 거리가 더 이상 줄어들지 않으면 종료
        else {
            break;
        }
    }

    // 최단 거리의 음하철도 좌표 출력
    cout << ansX << ' ' << ansY << '\n';
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘: 음하철도의 경로를 따라 이동하면서 현재 위치에서 최소 거리를 가지는 지점을 탐색합니다.
• 구현 세부사항:
  • gcd(dx, dy): 방향 벡터를 단위 벡터로 변환하여 경로가 정확히 표현되도록 합니다.
  • dis(xs, ys, xe, ye): 사람의 위치와 음하철도의 현재 위치 사이 거리의 제곱을 계산하여 최단 거리를 비교합니다.
  • 음하철도의 경로를 무한히 따라가면서 거리가 더 이상 줄어들지 않는 순간 루프를 종료합니다.
• 시간 복잡도 분석:
  • 최대 반복 횟수는 음하철도가 사람의 위치에서 거리를 줄일 수 있는 만큼 진행하므로 O(k) (k는 이동 횟수)입니다.
  • 거리 계산은 O(1)이므로, 전체 시간 복잡도는 O(k)입니다.

---

결과

사람의 위치에서 음하철도의 최단 거리 지점을 정확히 계산하여 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!