BOJ 11067 모노톤길 [Java]

BOJ 11067 모노톤길

1. 문제 링크

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

2. 문제 해설

문제에서 설명한 모노톤길의 정의에 의해 x 좌표 방향으로는 무조건 증가한다. 다만, y 좌표의 경우에는 길의 모양에 따라 증가할 수도 있고 감소할 수도 있다. 그렇기 때문에, y축 방향으로 어떻게 정렬을 해주는 지가 이 문제의 핵심이다. 문제 풀이의 흐름을 아래에서 설명하겠다.

1. 일단 입력 받은 좌표들을 x 좌표 오름차순으로 정렬하고, x 좌표가 같다면 y 좌표 오름차순으로 정렬한다.

2. 현재 정렬된 좌표 순서에 따라 모노톤길을 처음부터 따라간다고 생각해보자. 6번 (3, 3) 좌표에서 7번 좌표를 갈 때 (5, 3)으로 가는 것을 기대하지만, 현재 정렬된 순서에 따르면 (5, -1) 이 7번 좌표가 된다. 즉, 모노톤길이 y축 방향으로 아래로 감소하며 진행될 때 문제가 생긴다. 1번 과정에서 x 좌표가 같을 때, y 좌표를 오름차순으로 정렬했기 때문이다. 앞선 예시에서의 해결방법은 x 좌표가 5인 점들의 순서를 뒤집으면 된다.

3. 그렇다면 순서를 어떻게 뒤집을지 생각해보자. 1번 과정에서 정렬된 순서대로 시작점부터 모노톤길을 따라가보겠다.
현재 방문한 점이 이전 점과 x 좌표가 같다면 정상적으로 모노톤길을 가고 있는 것이므로 다음 점으로 이동한다.
또한, 같은 방식으로 현재 방문한 점이 이전 점과 y 좌표가 같다면 정상적으로 모노톤길을 가고 있는 것이므로 다음 점으로 이동한다.
다시 한번 말하지만, y축 방향으로 감소할 때가 문제인데 이 구간의 시작점은 이전 점과 x 좌표와 y 좌표가 모두 다르다. 그러므로 현재 방문한 점이 이전 점과 x, y축이 모두 다르면 y축 방향으로 감소하는 구간의 시작이라고 할 수 있다.
우리는 이 y축 방향으로 감소하는 구간의 순서를 뒤집어줘야하므로 끝점을 알아내야한다. y축으로 감소하는 구간은 x 좌표가 모두 같으므로 x좌표가 변하면 구간이 끝났다고 할 수 있다. 이런 식으로 구간의 시작점과 끝점을 구했다면 순서를 뒤집어준다.

4. 다만 주의할 점이 있다. 모노톤길의 시작점 (0, 0)부터 바로 y축으로 감소하는 구간이 시작되는 경우이다. 이 경우 이전 점이 없으므로 위에서 우리가 작성한 알고리즘 흐름으로는 y축으로 감소하는 구간이라고 인식할 수 없다. 그러므로 (0, 0) 이전의 점으로 (-1, 0)을 가상으로 미리 넣어주자.

3. 코드 보기

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

public class Main {
    static class Point implements Comparable<Point> {
        int x, y;

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

        @Override
        public int compareTo(Point o) {
            if (this.x < o.x) {
                return -1;
            } else if (this.x == o.x) {
                return this.y < o.y ? -1 : 1;
            } else {
                return 1;
            }
        }
    }

    static int t;
    static List<Point> cafe;

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

        t = Integer.parseInt(br.readLine());

        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            cafe = new ArrayList<>();
            cafe.add(new Point(-1, 0));

            for (int i = 0; i < n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());

                cafe.add(new Point(x, y));
            }

            Collections.sort(cafe);

            int idx = 1;

            while (idx <= n) {
                if (cafe.get(idx).x == cafe.get(idx - 1).x) {
                    idx++;
                } else if (cafe.get(idx).y == cafe.get(idx - 1).y) {
                    idx++;
                } else {
                    int cur = idx;
                    int curX = cafe.get(idx).x;

                    while (idx <= n && curX == cafe.get(idx).x) {
                        idx++;
                    }

                    List<Point> subList = cafe.subList(cur, idx);
                    Collections.reverse(subList);
                }
            }

            StringTokenizer st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());

            for (int i = 0; i < m; i++) {
                int cafeNum = Integer.parseInt(st.nextToken());
                sb.append(cafe.get(cafeNum).x).append(' ').append(cafe.get(cafeNum).y).append('\n');
            }
        }

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}