[백준] 2836번 수상 택시 (JAVA)

문제

- 집은 0번부터 M번까지 강을 따라 번호가 매겨져 있음

- 인접한 집 사이의 거리는 모두 1 킬로미터

- 상근이는 0번 집 거주. 보트를 이용하여 사람들 운송

- 저녁까지 M번 집으로 이동해야 함

- 상근이가 M번 집으로 가는 길에 사람들을 태워주려 함

- 상근이가 모든 사람을 데려다주고 M번 집으로 가기 위해서 이동해야 하는 거리의 최솟값 구하기

 

해결방법

문제는 쉽게 접근할 수 있었지만 또 자료형 실수를 했다.. 그냥 맨날 int로 때려박는거 다 들킴..

아무튼 문제로 돌아가면, 상근이가 0번에서 M번으로 이동하는 중에 사람들을 함께 운송하고 있는데, 0->M 이동하는 방향 대로 운송을 원하는 사람은 따질 필요가 없다. 어차피 가는 길에 얻어타는 느낌이니까..?

그래서 역주행을 원하는 사람들에 대해서 계산 해주기 위해 출발지보다 목적지가 작은 숫자를 가진 Taxi 객체를 destinations 리스트에 담아줄 수 있도록 하였다. 그래서 목적지를 기준으로 오름차순 정렬을 할 수 있도록 compareTo method를 override 해주었다. 

목적지를 기준으로 정렬한 이유는 최소한으로 움직여야하기 때문에 끊어지지 않는 선에서 최소한으로 거리를 측정해주기 위해서이다. 

예제 2를 예로 들면 역주행을 원하는 사람들의 좌표는 [(출발, 도착)] (3, 1), (4, 2), (12, 11), (14, 11), (14, 13)이다. 최적의 루트를 생각해보면 4번 집에서 태우고 3번에서 태웠던 사람 1번에 내려주고 4번에서 태운 사람 2번에 내려주고 다시 주행을 하다가, 12번, 14번에서 사람들을 태우고 11번, 13번으로 운송해주는 것이 가장 적은 거리를 왔다갔다할 수 있다. 그렇기 때문에 현재 보고 있는 범위 내에 목적 좌표가 포함되어 있다면 어디까지 갔다가 되돌아와야하는지 표시해주는 big 변수를 update해주고, 범위 내에 속하지 않으면 이전까지 체크했던 범위만큼 왔다갔다(2번)하는 거리를 계산해준다.

 

코드

import java.io.*;
import java.util.*;

// 수상 택시 클래스
class Taxi implements Comparable<Taxi>{
    long start;
    long end;

    public Taxi(long start, long end) {
        this.start = start;
        this.end = end;
    }

    // 목적지를 기준으로 정렬(목적지가 같다면 출발지를 기준으로 정렬)
    @Override
    public int compareTo(Taxi o) {
        if(this.end == o.end) return (int)(this.start - o.start);
        else return (int)(this.end - o.end);
    }
}

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long N = Integer.parseInt(st.nextToken());
        long M = Integer.parseInt(st.nextToken());
        long result = M;
        List<Taxi> destinations = new ArrayList<>();		// 역주행을 원하는 승객 택시 정보 리스트

        for(int i = 0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            // 역주행을 원하는 승객 택시 정보 리스트
            if(start > end) {
                destinations.add(new Taxi(start, end));
            }
        }
		
        // 위에서 정의한 기준에 따라 정렬
        Collections.sort(destinations);

	// 한 번에 왔다갔다 할 수 있는 범위를 구하기 위한 변수
        long small = destinations.get(0).end;
        long big = destinations.get(0).start;

        for(int i = 1; i<destinations.size(); i++){
            // 다음 승객 정보
            long start = destinations.get(i).end;
            long end = destinations.get(i).start;

	    // 다음 승객의 목적지가 한 번에 왔다갔다 할 수 있는 범위 내에 속한다면,
            // 그 승객의 출발지부터 다시 역주행하면 되기 때문에 해당 변수 Update
            if(start <= big) big = Math.max(big, end);
            // 한 번에 왔다갔다 할 수 있는 범위를 넘어섰다면,
            else {
            	// 한 번에 왔다갔다(2) 할 수 있었던 거리 계산
                result += 2 * (big - small);
                // 새로 범위 특정하기 위해서 범위 변수 update
                small = start;
                big = end;
            }
        }
		
        // 마지막에 특정한 범위에 대한 거리 계산
        result += 2 * (big - small);

	// 최소 거리 출력
        System.out.println(result);

    }
}