[BOJ] 백준 10655 - 마라톤 1 풀이

1. 문제

https://www.acmicpc.net/problem/10655

10655번: 마라톤 1

 

2. 풀이

백준 실버 3에 해당하는 문제이다. 생각보다 쉬운 문제를 삽질을 너무 많이 한 문제이다. 

1. 첫 번째 삽질
처음 문제를 풀 때 "모든 체크 포인트를 순서대로 방문한 후"를 못 보고 모든 체크 포인트를 방문했을 때 가장 최소로 걸리는 길을 찾는 문제로 봐서 다익스트라로 해결하려 했다. (문제를 제대로 좀 읽자... 제발...)

2. 브루트포스 확인
건너뛰려는 포인트를 하나씩 잡고 그때마다 이중 반복문을 돌려 거리를 구했다. 정답은 나왔지만, 최악의 경우 100,000 * 99,999번을 탐색해야 하므로 시간 초과가 났다.

3. 정답
우선 모든 체크 포인트를 순서대로 방문했을 때 이동 거리를 구한 후, 건너 뛸 체크 포인트를 하나씩 탐색한 후 작업을 진행했다.
예를 들어 i번 째 체크 포인트를 건너 뛴다고 했을 때, (i, i - 1) - (i, i + 1) + (i -1, i + 1)을 해주면 i번 째 체크 포인트를 건너 뛴 거리가 나오게 된다. 이를 아까 구한 전체 거리에서 빼준다면 i번 째 체크 포인트를 건너 뛴 총 이동 거리가 나온다.

3. 소스코드

1. 브루트포스 확인 코드(시간 초과)

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static List<Point> pointList = new ArrayList<>();
    static int pointCnt;
    static Point oldPoint;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        pointCnt = Integer.parseInt(br.readLine());
        for (int i = 0; i < pointCnt; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            pointList.add(new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        int result = Integer.MAX_VALUE;
        for (int i = 1; i < pointCnt - 1; i++) {
            int sum = 0;
            int[] visited = new int[pointCnt];
            visited[i] = 2;

            oldPoint = pointList.get(0);
            visited[0] = 1;

            for (int j = 1; j < pointCnt; j++) {
                if (j == i || visited[j] == 1) {
                    continue;
                } else {
                    sum += distanceHap(j);
                    oldPoint = pointList.get(j);
                    visited[j] = 1;
                }
            }

            result = Math.min(result, sum);
        }

        bw.write(Integer.toString(result) + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    static int distanceHap(int idx) {
        return Math.abs(pointList.get(idx).x - oldPoint.x) + Math.abs(pointList.get(idx).y - oldPoint.y);
    }
}

2. 정답 코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static List<Point> pointList = new ArrayList<>();
    static int pointCnt;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        pointCnt = Integer.parseInt(br.readLine());
        for (int i = 0; i < pointCnt; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            pointList.add(new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        int sum = 0;
        for (int i = 0; i < pointCnt - 1; i++) {
            sum += distanceHap(i, i + 1);
        }

        int result = sum;
        for (int i = 1; i < pointCnt - 1; i++) {
            int loopSum = sum - (distanceHap(i, i + 1) + distanceHap(i, i - 1)) + distanceHap(i - 1, i + 1);

            result = Math.min(loopSum, result);
        }

        bw.write(Integer.toString(result) + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    static int distanceHap(int first, int second) {
        return Math.abs(pointList.get(first).x - pointList.get(second).x) + Math.abs(pointList.get(first).y - pointList.get(second).y);
    }
}