[백준, Java] 1393번, 음하철도 구구팔(유클리드 호재법)

문제 링크

1393번: 음하철도 구구팔

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 정류장은 Xs, Ys에 존재하며, 시작 위치와 열차가 1초동안 움직이는 시간이 주어집니다.

2. 열차에서 내리는 뛰어내리는 위치는 정수입니다.

3. 열차에서 뛰어내리는 위치 기준 최단 거리인 x, y좌표 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 열차가 이동할 수 있는 최소 거리를 최대 공약수를 통해 구한 뒤 정류장까지 열차가 이동할 때 최단 거리를 탐색합니다.

 

3. 탐색을 통해 얻은 최단 거리일 때 좌표를 결과로 출력합니다.

 

 

열차 이동 최소 거리 구하기(유클리드 호재법, 최대 공약수)

 

백준이가 뛰어내릴 때 1초를 기준으로 뛰어내리는 것이 아니기 때문에 열차가 1초 단위의 움직임에 맞출 필요가 없습니다.

 

또한, (x, y)좌표가 정수가 되어야 하기 때문에 움직일 때에는 정수로 움직여야 합니다.

 

즉, 열차가 정수 기준 움직이는 최소 거리를 구해서 정류장까지의 최단 거리를 구해야 합니다. 

 

열차의 이동이 (x, y)으로 동시에 움직이기 때문에 각  dx, dy는 정비례해서 움직이게 됩니다.

 

dx, dy의 공약수가 존재한다면 공약수로 나눌 경우에도 이동하는 비율이 동일할 뿐만 아니라 정수의 형태입니다.

 

→ 최소 정수 움직임 거리를 구하기 위해 dx, dy에 대한 최대 공약수를 구해서 각각 나누어주면 최소 정수 움직임 거리가 됩니다.

 

여기서 최대 공약수는 유클리드 호재법을 이용해서 구현하였습니다.

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

정류장까지 최단 거리 구하기(완전 탐색)

 

정수 최소 이동 거리를 구하였다면 이제는 정류장까지의 최단 거리를 구해야 합니다.

 

열차 현재 위치를 기준으로 열차는 무한정 이동하기 때문에 한 번 정류장까지 거리가 멀어지기 시작하면 계속 멀어질 수 밖에 없습니다.

 

즉, 현재 위치에서 최소 이동 거리를 탐색하여 최단 거리를 탐색하고, 만약 정류장까지 거리가 현재 최단 거리보다 커지면 더 이상 탐색하지 않아도 됩니다.

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

Xs	Ys
5	2

Xe	Ye	dx	dy
2	1	2	4

 

 

2. 열차가 이동할 수 있는 최소 거리를 최대 공약수를 통해 구한 뒤 정류장까지 열차가 이동할 때 최단 거리를 탐색합니다.

 

열차 최소 이동 거리 구하기.

 

dx : 2

 

dy : 4

 

 

최대 공약수 : gcd(2, 4) = 2

 

x좌표 최소 이동 거리 : dx ÷ 2 = 2 ÷ 2 = 1

 

y좌표 최소 이동 거리 : dy ÷ 2 = 4 ÷ 2 = 2

 

 

 

열차 시작 위치에서 움직이면 정류장까지 최단 거리 구하기.

 

시작 위치 기준 정류장까지 최단 거리 : (5 - 2)² + (2 - 1)² = 10(√은 생략하겠습니다.)

 

 

열차 1번 이동했을 때 위치 : { (2+1), (1 + 2) } = (3, 3)

 

거리 구하기 : (3 - 2)² + (2 - 3)² = 2

 

→ 최단 거리 갱신!

 

열차가 2번 이동했을 때 위치 : { (2 + 2), (1 + 4) } = (4, 5)

 

거리 구하기 : (3 - 4)² + (2 - 5)² = 10

 

→ 최단 거리(2)보다 크기 때문에 이 이상 열차가 이동해도 최단 거리가 될 수 없습니다. 탐색 종료!

 

 

 

 

3. 탐색을 통해 얻은 최단 거리일 때 좌표를 결과로 출력합니다.

 

최단 거리 : 2

 

최단 거리일 때 좌표 : (3, 3)

 

3 3 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 이용해서 정류장 및 열차 정보를 띄어쓰기 기준 나누었습니다.
• gcd()을 통해 최대 공약수를 구해서 열차의 최소 정수 이동 거리를 구하였습니다.
• 최소 정수 이동 거리 기준 시작 위치부터 탐색하여 정류장까지의 최단 거리를 탐색합니다.
• 탐색을 통해 얻은 최단거리를 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• gcd 함수는 유클리드 호재법을 이용하여 최대 공약수를 구하도록 합니다.

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //입력값 저장
        int sx = Integer.parseInt(st.nextToken());
        int sy = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine()," ");
        int cx = Integer.parseInt(st.nextToken());
        int cy = Integer.parseInt(st.nextToken());
        int dx = Integer.parseInt(st.nextToken());
        int dy = Integer.parseInt(st.nextToken());
        //최대 공약수 구하기
        int gcd = gcd(Math.min(dx,dy),Math.max(dx,dy));
        //x, y 움직이는 최소 거리 계산
        dx /= gcd;
        dy /= gcd;
        //현재 위치에서 정류장까지 거리
        int minDistance = (sx - cx) * (sx - cx) + (sy - cy) * (sy - cy);
        int[] result = new int[2];
        result[0] = cx;
        result[1] = cy;
        //정류장까지의 최단 거리 탐색
        while(true){
            int nx = cx + dx;
            int ny = cy + dy;
            //현재 거리
            int distance = (sx - nx) * (sx - nx) + (sy - ny) * (sy - ny);
            //만약 최단 거리보다 커지면, 항상 더 멀어지기 때문에 탐색 종료.
            if(distance >= minDistance){
                break;
            }
            //최단 거리일 때
            minDistance = distance;
            result[0] = nx;
            result[1] = ny;
            cx = nx;
            cy = ny;
        }
        //탐색을 통해 얻은 최단 거리일 때 x, y좌표 BufferedWriter 저장
        bw.write(String.format("%d %d", result[0], result[1]));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //유클리드 호재법을 이용한 최대 공약수 구하는 함수
    static int gcd(int a, int b){
        if(a == 0){
            return b;
        }
        return gcd(b%a, a);
    }
}