[알고리즘 PS] 백준 9019번 DSLR 자바 문제풀이

문제

해당 포스팅은 백준의 9019번 DSLR 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

9019번: DSLR

 

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

 

문제 접근

 

이번 문제는 BFS 로 해결할 수 있는 재미있는 문제이다.

 

이 문제를 풀기 위해서 거의 3시간은 쏟았는데.. 계속해서 시간 초과 났던 문제다 ㅠㅠ

 

해결법

 

1 ~ 1만 까지 숫자가 존재할 때, 4가지 연산을 모두 수행해보면서 최소 횟수를 세면 된다.

 

처음에는 L과 R 연산에서 Shift 연산을 구현하기 위해서 String 클래스와 Arrays.stream() 을 함께 이용했었는데, 시간 초과가 났고 결국 블로그의 도움을 받아서 shift 연산을 수학적으로 해결했던 문제이다.

 

정답 코드

public class Main {

    private static int[] depth;
    private static int a;
    private static int b;

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

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

        while(t-- > 0) {

            String[] ab = br.readLine().split(" ");

            a = Integer.parseInt(ab[0]);
            b = Integer.parseInt(ab[1]);

            depth = new int[10000];

            bw.write(getCommand() + "\n");
        }

        bw.flush();
        bw.close();
    }

    private static String getCommand() {
        Queue<Pair> queue = new LinkedList<>();

        queue.add(new Pair("", a));
        depth[a] = 1;

        while(!queue.isEmpty()) {
            Pair front = queue.remove();

            if(front.number == b) {
                return front.command;
            }

            int l = l(front.number);
            if(depth[l] == 0) {
                depth[l] = depth[front.number] + 1;
                queue.add(new Pair(front.command+"L", l));
            }

            int r = r(front.number);
            if(depth[r] == 0) {
                depth[r] = depth[front.number] + 1;
                queue.add(new Pair(front.command+"R", r));
            }

            int d = d(front.number);
            if(depth[d] == 0) {
                depth[d] = depth[front.number] + 1;
                queue.add(new Pair(front.command+"D", d));
            }

            int s = s(front.number);
            if(depth[s] == 0) {
                depth[s] = depth[front.number] + 1;
                queue.add(new Pair(front.command+"S", s));
            }
        }
        return null;
    }

    private static int d(int n) {
        n *= 2;
        if(9999 < n) n %= 10_000;
        return n;
    }

    private static int s(int n) {
        if(n == 0) n = 9999;
        else n -= 1;
        return n;
    }

    private static int l(int n) {
        return n % 1000 * 10 + n / 1000;
    }

    private static int r(int n) {
        return n % 10 * 1000 + n / 10;
    }
}

class Pair {
    String command;
    int number;

    public Pair(String command, int number) {
        this.command = command;
        this.number = number;
    }
}

어떤 값이던 1 ~ 1만 사이로는 연산이 가능해서 return 을 null 로 해줘도 크게 문제가 없다.

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.