[백준]JAVA - 11067번: 모노톤길

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

11067번: 모노톤길

풀이

제한 시간이 5초로 엄청 길고, n의 범위가 최대 100,000 이므로 T의 값에 따라서 완전 탐색도 충분히 가능하다고 본다.
 
문제 조건에는 "x축의 값이 작아지는 경우는 없어도 출구까지 도달할 수 있다." 이다.
따라서 카페 방문 순서는 아래와 같다.
 
1. 현재 위치와 같은 x축에 있는 카페들 중 가까운 카페부터 방문한다.
2. 현재 위치와 같은 x축의 카페를 모두 방문했다면 y축이 동일한 카페들 중 가장 가까운 카페를 방문한다.
 
위와 같은 순서로 카페를 방문하려면 x축의 값을 오름차순으로 정렬해주고, x축이 같은 것들끼리 y축을 정렬해줘야된다.
y축을 정렬할 때는 오름차순, 내림차순은 상관이 없다.

public int compareTo (Pos o) {
    if (this.x > o.x) {
        return 1;
    } else if (this.x == o.x) {
        return this.y > o.y ? 1 : -1;
    } else {
        return -1;
    }
}

 
정렬을 끝낸 후에 첫번째 인덱스부터 차례대로 x, y축을 비교해준다. 체크해주는 과정에서 중요한 건 예시처럼 바로 오른쪽 방향으로 가는 게 아니라 위, 아래 방향으로 갔을 때 y축 값을 정렬했더라도 0에서 어떤 카페가 가장 가까운지 판단할 수 없기 때문에 시작값을 (-1, 0) 넣어줘야된다.

ArrayList<Pos> cafe = new ArrayList<>();
cafe.add(new Pos(-1, 0));

Collections.sort(cafe);
            
int idx = 1;
            
while (idx <= N) {
    // x축이 같은 경우
    if (cafe.get(idx).x == cafe.get(idx-1).x) {
        idx++;
                
    // y축이 같은 경우
    } else if (cafe.get(idx).y == cafe.get(idx-1).y) {
        idx++;
    } else {
        int cur = idx;
        int curX = cafe.get(idx).x;
                    
        // x축이 같아질 때까지
        while (idx <= N && curX == cafe.get(idx).x) {
            idx++;
        }
                    
        List<Pos> subList = cafe.subList(cur, idx);
        Collections.reverse(subList);
    }
}

위에서 x축을 오름차순으로 정렬했기 때문에 x축이 같다면 그냥 넘어가주면 된다. 

y축을 내림차순으로 정렬했다면 1번 y축과 같은 위로 올라갈 경우에 문제가 생길 것이고, 오름차순으로 정렬했다면 2번 y축과 같은 아래로 내려가는 경우에 문제가 생길 것이다.
 
문제가 생기는 이 부분을 찾아내서 subList를 이용해 reverse 시켜줘야된다.
 
<최종코드>

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

public class Main {
    public static class Pos implements Comparable<Pos>{
        int x, y;
        
        public Pos (int x, int y) {
            this.x = x;
            this.y = y;
        }
        
        public int compareTo (Pos o) {
            if (this.x > o.x) {
                return 1;
            } else if (this.x == o.x) {
                return this.y > o.y ? 1 : -1;
            } else {
                return -1;
            }
        }
    }
    
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스
        
        for (int i=0; i<T; i++) {
            int N = Integer.parseInt(br.readLine()); // 카페 개수
            
            ArrayList<Pos> cafe = new ArrayList<>();
            cafe.add(new Pos(-1, 0));
            
            for (int j=0; j<N; j++) {
                st = new StringTokenizer(br.readLine());
                
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                
                cafe.add(new Pos(x, y));
            }
            
            Collections.sort(cafe);
            
            int idx = 1;
            
            while (idx <= N) {
                // x축이 같은 경우
                if (cafe.get(idx).x == cafe.get(idx-1).x) {
                    idx++;
                
                // y축이 같은 경우
                } else if (cafe.get(idx).y == cafe.get(idx-1).y) {
                    idx++;
                } else {
                    int cur = idx;
                    int curX = cafe.get(idx).x;
                    
                    // x축이 같아질 때까지
                    while (idx <= N && curX == cafe.get(idx).x) {
                        idx++;
                    }
                    
                    List<Pos> subList = cafe.subList(cur, idx);
                    Collections.reverse(subList);
                }
            }
            
            st = new StringTokenizer(br.readLine());
            int M = Integer.parseInt(st.nextToken());
            
            for (int d=0; d<M; d++) {
                int tmp = Integer.parseInt(st.nextToken());
                System.out.println(cafe.get(tmp).x + " " + cafe.get(tmp).y);
            }
        }
    }
}