[BOJ. 2983] 개구리 공주

문제

트럭을 타고 이동하던 중에 상근이는 휴식을 취하기 위해서 호수에 잠시 들렸다. 호수에는 개구리가 살고 있고, 개구리는 호수 위에 떠있는 식물 N개를 점프하면서 다닌다. 오래된 전설에 따르면 개구리에게 키스를 하면 개구리는 아름다운 공주로 변한다고 한다. 일단 개구리를 잡아야 전설이 사실인지 아닌지 확인할 수 있다. 개구리를 잡아보자.

호수는 2차원 평면으로 생각할 수 있고, 식물은 그 평면 위의 점으로 나타낼 수 있다. (x, y)위에 있는 개구리는 아래 네 가지 방향 중 한 방향으로 점프할 수 있다.

임의의 양의 정수 P에 대해서, (x+P, y+P)로 점프할 수 있다. 이 방향을 A라고 한다.
임의의 양의 정수 P에 대해서, (x+P, y-P)로 점프할 수 있다. 이 방향을 B라고 한다.
임의의 양의 정수 P에 대해서, (x-P, y+P)로 점프할 수 있다. 이 방향을 C라고 한다.
임의의 양의 정수 P에 대해서, (x-P, y-P)로 점프할 수 있다. 이 방향을 D라고 한다.

개구리는 네 방향 중 한 방향을 고른다. 그 다음 그 방향에 있는 가장 가까운 식물로 점프를 한다. 만약, 고른 방향에 식물이 없다면, 개구리는

그 위치에 그대로 있는다. 개구리가 점프를 하고 난 이후에, 원래 있던 식물은 호수로 가라앉게되고 사라진다.

상근이는 식물의 위치와 개구리가 고른 방향을 모두 알고 있다. 상근이는 개구리의 점프가 끝나는 꽃의 좌표를 알아낸 다음, 거기서 개구리를 잡으려고 한다.

개구리의 점프가 끝나는 식물의 위치는 어디일까?

입력

첫째 줄에 식물의 수 N과 점프의 수 K가 주어진다. (1 ≤ N, K ≤ 100,000)
둘째 줄에는 개구리가 고른 방향 K개가 주어진다. 이 방향은 'A','B','C','D'로만 이루어져 있다.
셋째 줄부터 N개 줄에는 식물의 좌표가 X, Y가 주어진다. (0 ≤ X, Y ≤ 1,000,000,000) 처음으로 주어지는 식물에 개구리가 있다.

출력

개구리의 점프가 끝나는 식물의 좌표를 출력한다.

---

처음에는 평면 좌표를 그대로 사용하면서 풀었는데, 이 부분이 굉장히 어려웠고, 탐색 과정에서 시간 초과가 발생했다.
그래서 결국 gg.. 치고 답을 찾으러 갔다.

핵심 아이디어는 2차원 평면상의 좌표들을 직선으로 만들어 문제를 풀고, 해당 직선에 있으면 가장 가까운 곳으로 이동하도록 만드는 것이었다.

예를들면 아래와 같다.

원래 좌표계:
(0,2)  (1,1)  (2,0)
   ↖     ↖     ↖
(0,1)  (1,0)

변환 후 좌표 (x - y, x + y):
(0,2) → (-2,2)
(1,1) → (0,2)
(2,0) → (2,2)

이렇게 바뀌면 ↖ 방향 애들이 다 (x + y = 2)로 같은 선에 있다는 것이다!

정답 코드

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

public class Main {
    static Map<Integer, TreeSet<Integer>> xMap = new HashMap<>();
    static Map<Integer, TreeSet<Integer>> yMap = new HashMap<>();
    static int curX, curY;

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

        char[] dirs = br.readLine().toCharArray();

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

            xMap.computeIfAbsent(tx, k -> new TreeSet<>()).add(ty);
            yMap.computeIfAbsent(ty, k -> new TreeSet<>()).add(tx);

            if (i == 0) {
                curX = tx;
                curY = ty;
            }
        }

        for (char dir : dirs) {
            move(dir);
        }

        int finalX = (curX + curY) / 2;
        int finalY = (curY - curX) / 2;
        System.out.println(finalX + " " + finalY);
    }

    static void move(char dir) {
        if (dir == 'A') {
            TreeSet<Integer> set = xMap.get(curX);
            if (set == null) return;
            Integer next = set.higher(curY);
            if (next != null) {
                remove(curX, curY);
                curY = next;
            }
        } else if (dir == 'B') {
            TreeSet<Integer> set = yMap.get(curY);
            if (set == null) return;
            Integer next = set.higher(curX);
            if (next != null) {
                remove(curX, curY);
                curX = next;
            }
        } else if (dir == 'C') {
            TreeSet<Integer> set = yMap.get(curY);
            if (set == null) return;
            Integer next = set.lower(curX);
            if (next != null) {
                remove(curX, curY);
                curX = next;
            }
        } else if (dir == 'D') {
            TreeSet<Integer> set = xMap.get(curX);
            if (set == null) return;
            Integer next = set.lower(curY);
            if (next != null) {
                remove(curX, curY);
                curY = next;
            }
        }
    }

    static void remove(int x, int y) {
        TreeSet<Integer> ySet = xMap.get(x);
        if (ySet != null) {
            ySet.remove(y);
            if (ySet.isEmpty()) xMap.remove(x);
        }
        TreeSet<Integer> xSet = yMap.get(y);
        if (xSet != null) {
            xSet.remove(x);
            if (xSet.isEmpty()) yMap.remove(y);
        }
    }
}

 

 

좌표 평면 상에 있는 점을 직선 상으로 옮겨 찾는 방법을 알게되었다. 이후 다시 복습해서 이런 기술을 완전히 내것으로 만들어야겠다.