[코드트리/NOVICE MID] 마라톤 중간에 택시타기 2 (JAVA)

🔺 문제

 

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

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static Point[] arr;
    static int min = Integer.MAX_VALUE;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
        arr = 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());
 
            arr[i] = new Point(x, y);
        }
 
        // 모든 체크포인트 건너뛰며 최소 거리 계산
        for(int i = 1 ; i < N - 1 ; i++) {
            int tmpX = arr[i].x;
            int tmpY = arr[i].y;
 
            arr[i] = new Point(arr[i-1].x, arr[i-1].y); // 건너뛰기 위해 이전 값과 같은 값으로 저장해둠
 
            int dist = getDistance(arr);    // 거리 계산
            min = Math.min(min, dist);      // 최소 거리 갱신
            
            // 원상복구
            arr[i].x = tmpX;
            arr[i].y = tmpY;
        }
        
        System.out.println(min);
    }
 
    // 택시 거리 계산 
    private static int getDistance(Point[] p) {
        int distance = 0;
 
        for(int i = 0 ; i < N - 1 ; i++) {
            distance += (Math.abs(p[i + 1].y - p[i].y) + Math.abs(p[i + 1].x - p[i].x));
        }
        return distance;
    }
}
 
class Point {
    int x, y;
 
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

 

 

🧩  해결 아이디어

• 완전탐색 : 모든 점에 대해 건너뛰기 수행

 

0과 N번째 점을 제외한 모든 점에 대해 기존 값과 같은 값으로 좌표를 임시변경한다.

// 원상복구용 좌표
int tmpX = arr[i].x;
int tmpY = arr[i].y;

// 건너뛰기 위해 이전 값과 같은 값으로 저장해둠
arr[i] = new Point(arr[i-1].x, arr[i-1].y);

 

이 때의 택시 거리의 총합을 계산하고, 구한 택시 거리의 총합이 최솟값이라면, 최솟값을 갱신한다.

int dist = getDistance(arr);    // 거리 계산
min = Math.min(min, dist);      // 최소 거리 갱신

 

 

좌표를 원상복구 시켜준다.

// 원상복구
arr[i].x = tmpX;
arr[i].y = tmpY;

 

 

 

---

🔺 다른 풀이들

- 2중 for문으로 체크포인트의 인덱스가 같으면 거리 구하는 과정을 스킵하게 하였다... 이게 맞는 것 같음

import java.util.Scanner;
 
public class Main {
    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 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();
        }
        
        // 각 i번째 체크포인트 건너 뛰었을 때의 거리 계산
        int ans = Integer.MAX_VALUE;
 
        for(int i = 1; i < n - 1; i++) {
            int dist = 0;
            int prevIdx = 0;
 
            for(int j = 1; j < n; j++) {
                if(j == i) continue;
 
                dist += Math.abs(x[prevIdx] - x[j]) + Math.abs(y[prevIdx] - y[j]);
                prevIdx = j;
            }
 
            ans = Math.min(ans, dist);    // 가능한 거리 중 최솟값 계산
        }
        
        System.out.print(ans);
    }
}

 

 

---

💬 느낀 점

30분 안에 풀고 싶었는데..

37분 걸렸당...

쉬운 문제는 빠르게 풉시다ㅠ

 

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