[자바] 백준 3089 - 네잎 클로버를 찾아서 (java)

목차

• 문제 : boj3089
• 필요 알고리즘
• 풀이
• 코드 : github

문제 : boj3089

 

 

필요 알고리즘

• 매개변수 탐색(Parametric Search), 이분탐색, 정렬
  
  • 2차원에 대한 매개변수 탐색(이분탐색 응용)으로 풀 수 있는 문제이다. 이걸 위해 정렬이 필요하다.
• 시뮬레이션
  • M개의 명령에 대해 시뮬레이션을 돌려봐야 최종 결과를 알 수 있다.

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

 

 

풀이

  R, L, U, D 각각의 명령에 대해 필요한 동작은 다음과 같다.

R : 동일 Y축에서 우측으로 가장 가까운 점을 알 수 있으면 된다. 즉, Y값이 동일한 점 중 X값이 자신보다 큰 것 중 가장 작은걸 알아야 한다.

L : 동일 Y축에서 좌측으로 가장 가까운 점을 알 수 있으면 된다. 즉, Y값이 동일한 점 중 X값이 자신보다 작은것 중 가장 큰걸 알 수 있어야 한다.

U : 마찬가지로 X값이 동일한 점 중 Y값이 자신보다 큰 것 중 가장 작은걸 알아야 한다.

D : X값이 동일한 점 중 Y값이 자신보다 작은 것 중 가장 큰걸 알아야 한다.

 

  이걸 하기 제일 간단한 방법은 이분탐색을 응용한 매개변수 탐색을 사용하는건데, 2차원에 어떻게 적용할지 난감할 수 있다. 아주 무식한 방법으로 가능한데, 그냥 모든 Y축값에 대해 X값에 대한 매개변수 탐색, 모든 X축값에 대해 Y값에 대한 매개변수 탐색을 진행하면 된다. 이 경우 메모리는 다소 문제가 될 수 있어도 아무튼 시간복잡도는 O(MlogN)으로 해결 된다. 그리고 사실 N이 최대 10만이라 메모리도 크게 문제되지 않는다.

 

  약간 말로 설명하자면 복잡하긴한데, 매개변수 탐색 방법을 알고 있다면 이하 코드의 주석을 보면 이해할 수 있을 것 같다.

Map<Integer, TreeSet<Pos>> rMap = new HashMap<>();	// 모든 Y축에 대해 X값 매개변수 탐색용
Map<Integer, TreeSet<Pos>> cMap = new HashMap<>();	// 모든 X축에 대해 Y값 매개변수 탐색용

while (n-->0) {	// N개의 좌표를 입력 받는다.
    st = new StringTokenizer(br.readLine());
    int c = Integer.parseInt(st.nextToken());
    int r = Integer.parseInt(st.nextToken());
    // 내 경우 X, Y는 헷갈려서 R과 C로 주로 바꿔 쓴다. R이 Y축, C가 X축이다.

    if (!rMap.containsKey(r)) rMap.put(r, new TreeSet<>((o1, o2) -> o1.c - o2.c));
    // 동일 Y축에 대해 X값 매개변수 탐색을 하기위해, X값을 기준으로 정렬해준다.
    if (!cMap.containsKey(c)) cMap.put(c, new TreeSet<>((o1, o2) -> o1.r - o2.r));
	// 동일 X축에 대해 Y값 매개변수 탐색을 하기위해, Y값을 기준으로 정렬한다.

    Pos pos = new Pos(r, c);
    rMap.get(r).add(pos);
    cMap.get(c).add(pos);
}

String dir = br.readLine();
Pos cur = new Pos(0, 0);
for (int i = 0; i < m; i++) {
    switch (dir.charAt(i)) {
        case 'R': cur = rMap.get(cur.r).higher(cur); break;	
        // R일 경우 동일한 Y값에서(get(cur.r)), 더 크면서 가장 작은 X값을 가진 녀석을 찾는다(higher(cur)).
        case 'L': cur = rMap.get(cur.r).lower(cur); break;
        // 이하 'R' 설명과 동일한 방식이다.
        case 'U': cur = cMap.get(cur.c).higher(cur); break;
        case 'D': cur = cMap.get(cur.c).lower(cur); break;
    }
}
System.out.println(cur);	// 최종 위치를 출력한다.

 

 

코드 : github

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

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();
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        Map<Integer, TreeSet<Pos>> rMap = new HashMap<>();
        Map<Integer, TreeSet<Pos>> cMap = new HashMap<>();

        while (n-->0) {
            st = new StringTokenizer(br.readLine());
            int c = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());

            if (!rMap.containsKey(r)) rMap.put(r, new TreeSet<>((o1, o2) -> o1.c - o2.c));
            if (!cMap.containsKey(c)) cMap.put(c, new TreeSet<>((o1, o2) -> o1.r - o2.r));

            Pos pos = new Pos(r, c);
            rMap.get(r).add(pos);
            cMap.get(c).add(pos);
        }

        String dir = br.readLine();
        Pos cur = new Pos(0, 0);
        for (int i = 0; i < m; i++) {
            switch (dir.charAt(i)) {
                case 'R': cur = rMap.get(cur.r).higher(cur); break;
                case 'L': cur = rMap.get(cur.r).lower(cur); break;
                case 'U': cur = cMap.get(cur.c).higher(cur); break;
                case 'D': cur = cMap.get(cur.c).lower(cur); break;
            }
        }
        System.out.println(cur);
    }
}

class Pos {
    int r, c;

    public Pos(int r, int c) {
        this.r = r;
        this.c = c;
    }

    @Override
    public String toString() {
        return c + " " + r;
    }
}