[자바] 백준 2836 - 수상 택시 (java)

목차

문제 : boj2836

 

 

필요 알고리즘

• 정렬, 스위핑
  
  • 사실 그냥 정렬 + 반복문 + 조건문만 알면 풀 수 있다. 아이디어가 더 중요한 문제다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  아이디어만 잘 떠올리면 풀 수 있는 문제이다. 내 경우 이하와 같이 진행했다.

 

  어차피 0부터 M까진 무조건 가야 한다. 따라서 입력값에서 타는 위치가 목적지보다 이전이라면, 사실 신경을 안써도 된다. 언제 내렸던 탔던 상관 없다. 그러므로 역방향으로 되돌아와야 하는 경우만 데이터로 남기면 된다.

 

  그럼 이제 역방향(목적지가 타는 위치보다 이전이라, 탄 후 되돌아와야 하는 녀석들)들만 가지고 어떤 경우가 최단거리일 지 생각해보면 된다.

 

case 1. M이 10이고 데이터가 1개인데, 3에서 타서 1로 되돌아와야 한다고 해보자.

  이 경우 단순히 0 -> 3 -> 1 -> 10 으로 진행하면 된다. (총 14)

 

 

case 2. M이 10이고 데이터가 2개인데, 3->1이 하나 있고, 6->2가 하나 있다고 해보자.

  이 경우 0 -> 3 -> 2 -> 6 -> 2 -> 10 을 하는 것 보다 (총 22)

 

  아래처럼 0 -> 6 -> 1 -> 10 을 하는 것이 더 이득이다. (총 20) 위는 [2, 3] 구간을 2번 왔다갔다 해버린 셈이므로, '2' 만큼 더 길어진거다.

 

 

case 3. 그럼 이번엔 M이 10이고 데이터가 2개인데, 3->1이 하나 있고, 9->8이 하나 있다고 해보자.

  '2'에선 2개를 동시에 처리하는게 이득이었는데, '3'에선 당연하게도 따로 처리하는게 이득이다. 즉, 위보다 아래가 더 최단거리이다. (위는 총 26, 아래는 총 16)

 

 

  위에서 case로 설명한걸 말로 설명해보자면, 출발지와 목적지가 서로 겹치는 구간들은 그룹으로 생각해서 동시에 처리하는게 이득이다(case2). 서로 겹치지 않는 그룹들은 따로 처리하는게 이득이다 (case3).

 

1. 입력받은 데이터들 중 역방향만 남긴다.

List<Human> humans = new ArrayList<>();
while (n-->0) {
    st = new StringTokenizer(br.readLine());
    int from = Integer.parseInt(st.nextToken());
    int to = Integer.parseInt(st.nextToken());
    if (from <= to) continue;	// 역방향 아닌건 버린다.

    humans.add(new Human(from, to));
}

 

 

2. 역방향 데이터를 목적지를 기준으로 정렬한다. (그룹을 정하기 쉽게 하기 위함이다. 그냥 서로소 집합(union-find) 같은거 써도 상관없다.)

humans.sort(Comparator.comparingInt(o -> o.to));

 

 

3. 서로 다른 그룹이라면 기존 그룹 사이즈x2 (뒤로 돌아왔다가 다시 앞으로 가야하므로 x2임) 만큼 결과에 더해준다.

if (groupEd < cur.to) {
    ans += (groupEd - groupSt) * 2L;
    groupSt = cur.to;
    groupEd = cur.from;
    continue;
}

 

 

4. 서로 겹치는 그룹이라면, 그룹 사이즈를 체크해준다.

groupEd = max(groupEd, cur.from);
groupSt = min(groupSt, cur.to);

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

import static java.lang.Math.max;
import static java.lang.Math.min;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        List<Human> humans = new ArrayList<>();
        while (n-->0) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            if (from <= to) continue;

            humans.add(new Human(from, to));
        }
        humans.sort(Comparator.comparingInt(o -> o.to));

        long ans = m;
        int groupSt = humans.get(0).to;
        int groupEd = humans.get(0).from;
        for (Human cur : humans) {
            if (groupEd < cur.to) {
                ans += (groupEd - groupSt) * 2L;
                groupSt = cur.to;
                groupEd = cur.from;
                continue;
            }

            groupEd = max(groupEd, cur.from);
            groupSt = min(groupSt, cur.to);
        }
        ans += (groupEd - groupSt) * 2L;

        System.out.println(ans);
    }
}

class Human {
    int from;
    int to;

    public Human(final int from, final int to) {
        this.from = from;
        this.to = to;
    }
}