백준 11067 모노톤길 자바(java)

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

11067번: 모노톤길

 

풀이 방법

주어진 문제에서 기억해야할 것은

1. x 축 값이 작아지는 경우가 없다. 즉, x 축을 되돌아가지 않는다.

2. 코너에서만 90 도 각도로 왼쪽, 오른쪽 회전이 가능하다. 즉,  y 축에서 이동 시 한 방향으로만 간다.

3. 수평, 수직 이동만 가능하다. 즉, x 좌표가 달라지면 y 좌표가 같아야 한다. 

    (3, 3) -> (5, 3) 이동은 가능하지만, (3, 3) -> (5, -1) 이동은 수평이 아니므로 불가

 

1번의 의미: x 좌표를 기준으로 오름차순 정렬해야 한다.

2번의 의미: x 좌표가 달라질 때까진 하나의 방향으로만 쭉 가므로 y 좌표가 정렬되어야 한다.

3번의 의미: x 좌표가 달라질 때 이전 카페와 y 좌표가 같은지의 비교가 필요하다.

 

예제 입력 1을 예로 들어 설명한다.

위 사항들을 만족하기 위해 먼저 카페들을 x 좌표를 오름차순으로, x 좌표가 같다면 y 좌표를 오름차순 정렬한다. 정렬한 결과 ... -> (2, 1) -> (3, 1) -> (3, 3) -> (5, -1) -> (5, 1) -> (5, 3) -> (6, -1)... 순서가 된다.

x 좌표가 달라질 때는 y 좌표가 같아야 한다.

(2, 1) -> (3, 1) -> (3, 3) 경우 x 좌표가 달라질 때 y 좌표가 1로 같으므로 그대로 이동이 가능하다.

하지만, (3, 3) -> (5, -1) -> (5, 1) -> (5, 3) 의 경우 x 좌표가 달라질 때  y 좌표가 3 과 -1 로 다르므로 이동이 불가하다. 이 경우 오름차순이 아닌 내려가는 방향임을 의미한다. 따라서 x 축이 같은 카페들을 y 좌표 내림차순으로 정렬하여 (3, 3) -> (5, 3) -> (5, 1) -> (5, -1) 이 되도록 만들어 주어야 한다. 

따라서 x 축이 같은 카페들의 방향 판단이 중요하다. x 축이 같은 카페들을 임시 리스트에 저장해놓고 x 좌표가 다른 카페가 나올 때 직전에 부여한 번호의 카페 y 좌표와 임시 리스트의 첫번째 카페의 y 좌표를 비교하여 같으면 올라가는 방향이므로 그대로, 다르면 내려가는 방향이므로 y 좌표 내림차순 정렬하여 번호를 부여하면 된다.

 

주의할 점!

(0, 0), (0, -1), (0, -2) 와 같이 x 가 0 이고 y가 음수인 좌표가 입력되는 경우

처음에 x 좌표를 오름차순으로, y 좌표를 오름차순 정렬하므로 (0, -2) -> (0, -1) -> (0, 0) 이 된다.

입구가 (0, 0) 이므로  (0, 0) -> (0, -1) -> (0, -2) 와 같이 y 좌표 내림차순으로 정렬이 가능하려면

처음에 (-1, 0) 인 카페가 존재한다고 가정하고 리스트에 삽입해주고 탐색을 시작해야 한다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int i=0; i<T; i++) {
            int n = Integer.parseInt(br.readLine());
            // n개의 카페 좌표 입력
            int[][] arr = new int[n][2];
            for(int j=0; j<n; j++) {
                String[] pos = br.readLine().split(" ");
                arr[j][0] = Integer.parseInt(pos[0]);
                arr[j][1] = Integer.parseInt(pos[1]);
            }
            String[] goal = br.readLine().split(" "); // 출력해야 하는 카페 번호 입력

            // x 좌표 오름차순 정렬
            Arrays.sort(arr, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    // x 좌표 오름차순 정렬, x 좌표가 같으면 y 좌표를 오름차순으로 정렬
                    return (o1[0] == o2[0]) ? o1[1] - o2[1] : o1[0] - o2[0];
                }
            });

            List<int[]> cafeList = new ArrayList<>(); // 배치된 카페 리스트
            List<int[]> sameX = new ArrayList<>(); // x 좌표가 같은 카페를 저장하는 임시 리스트
            cafeList.add(new int[]{-1, 0}); // 가상의 카페

            for(int j=0; j<n; j++) {
                // 이전과 x 좌표가 같은 카페라면
                if(j > 0 && arr[j-1][0] == arr[j][0]) {
                    sameX.add(arr[j]);

                } else { // x 좌표가 달라질 때
                    // 현재까지 x 좌표가 같았던 카페들을 배치하기
                    // 배치 완료된 마지막 번호 카페의 y 좌표와 배치해야 할 sameX 리스트의 첫번째 카페의 y 좌표 비교
                    if(!sameX.isEmpty() && cafeList.get(cafeList.size()-1)[1] != sameX.get(0)[1]) { // y좌표가 다르다면
                        // y 좌표 내림차순으로 뒤집기
                        reverse(sameX);
                    }
                    cafeList.addAll(sameX);
                    sameX.clear();
                    sameX.add(arr[j]);
                }
            }

            // 마지막에 x 좌표가 계속 같다면 sameX 리스트의 카페들이 배치 안되므로 그럴 경우 처리
            if(cafeList.size() != n+1) {
                if(cafeList.get(cafeList.size()-1)[1] != sameX.get(0)[1]) {
                    reverse(sameX);
                }
                cafeList.addAll(sameX);
            }
            // 카페 번호에 맞는 좌표 출력하기
            for(int j=1; j<goal.length; j++) {
                int cafeNum = Integer.parseInt(goal[j]);
                int[] cafePos = cafeList.get(cafeNum);
                System.out.println(cafePos[0] + " " + cafePos[1]);
            }
        }
    }

    // 카페들을 y 좌표 기준 내림차순으로 정렬
    public static void reverse(List<int []> list) {
        Collections.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[1] - o1[1];
            }
        });

    }
}