[JAVA] BOJ 백준 9019번 - DSLR

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

---

2. 내가 푼 방법

최소한의 명령어가 반환되도록 풀어야 하므로 BFS 문제이다.

따라서 큐를 이용해 BFS 알고리즘을 구현했고, 각 명령에 따라 함수를 만들어 명령을 수행한 결과가 반환되도록 구현했다.

public static String dfs (int from, int to) {
    String result = "";

    Queue<Tuple> queue = new LinkedList<>();
    queue.add(new Tuple(from, ""));

    boolean[] check = new boolean[MAX];

    while (!queue.isEmpty()) {
        Tuple tuple = queue.poll();
        int num = tuple.num;
        String command = tuple.command;

        if (check[num]) continue;
        if (num == to) {
            result = command;
            break;
        }

        check[num] = true;

        StringBuilder sb = new StringBuilder(command);
        queue.add(new Tuple(commandD(num), sb.append('D').toString()));
        queue.add(new Tuple(commandS(num), sb.deleteCharAt(sb.length()-1).append('S').toString()));
        queue.add(new Tuple(commandL(num), sb.deleteCharAt(sb.length()-1).append('L').toString()));
        queue.add(new Tuple(commandR(num), sb.deleteCharAt(sb.length()-1).append('R').toString()));
    }

    return result;
}

 

문제에서 중요한 부분은 네 자릿수를 가진다는 것이다. 따라서 각 명령을 수행할 때 나는 문자열로 변환해 주어 계산했기 때문에 R 명령과 L 명령에서 네 자릿수가 안된다면 0을 채워 넣는 것이 중요했던 것 같다.

public static int commandD (int from) {
    from *= 2;

    if (from >= MAX) from %= MAX;

    return from;
}

public static int commandS (int from) {
    from -= 1;

    if (from < 0) from = MAX-1;

    return from;
}

public static int commandL (int from) {
    StringBuilder sb = new StringBuilder(String.valueOf(from));
    while (sb.length() < 4) {
        sb.insert(0, 0);
    }

    sb.append(sb.charAt(0)).deleteCharAt(0);

    return Integer.parseInt(sb.toString());
}

public static int commandR (int from) {
    StringBuilder sb = new StringBuilder(String.valueOf(from));

    while (sb.length() < 4) {
        sb.insert(0, 0);
    }

    sb.insert(0, sb.charAt(sb.length()-1));
    sb.deleteCharAt(sb.length()-1);

    return Integer.parseInt(sb.toString());
}

---

3. 자바 코드

깃허브 풀이 주소

https://github.com/geujeog/BOJ/blob/main/B9019.java

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

class Main {
    static int MAX = 10000;

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

        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            bw.write(dfs(from, to)+"\n");
        }

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

    public static String dfs (int from, int to) {
        String result = "";

        Queue<Tuple> queue = new LinkedList<>();
        queue.add(new Tuple(from, ""));

        boolean[] check = new boolean[MAX];

        while (!queue.isEmpty()) {
            Tuple tuple = queue.poll();
            int num = tuple.num;
            String command = tuple.command;

            if (check[num]) continue;
            if (num == to) {
                result = command;
                break;
            }

            check[num] = true;

            StringBuilder sb = new StringBuilder(command);
            queue.add(new Tuple(commandD(num), sb.append('D').toString()));
            queue.add(new Tuple(commandS(num), sb.deleteCharAt(sb.length()-1).append('S').toString()));
            queue.add(new Tuple(commandL(num), sb.deleteCharAt(sb.length()-1).append('L').toString()));
            queue.add(new Tuple(commandR(num), sb.deleteCharAt(sb.length()-1).append('R').toString()));
        }

        return result;
    }

    public static class Tuple {
        int num;
        String command;

        public Tuple (int num, String command) {
            this.num = num;
            this.command = command;
        }
    }

    public static int commandD (int from) {
        from *= 2;

        if (from >= MAX) from %= MAX;

        return from;
    }

    public static int commandS (int from) {
        from -= 1;

        if (from < 0) from = MAX-1;

        return from;
    }

    public static int commandL (int from) {
        StringBuilder sb = new StringBuilder(String.valueOf(from));
        while (sb.length() < 4) {
            sb.insert(0, 0);
        }

        sb.append(sb.charAt(0)).deleteCharAt(0);

        return Integer.parseInt(sb.toString());
    }

    public static int commandR (int from) {
        StringBuilder sb = new StringBuilder(String.valueOf(from));

        while (sb.length() < 4) {
            sb.insert(0, 0);
        }

        sb.insert(0, sb.charAt(sb.length()-1));
        sb.deleteCharAt(sb.length()-1);

        return Integer.parseInt(sb.toString());
    }
}

---

4. 결과 및 회고

각 명령을 수행할 때 문자열로 변환하지 말고, 문제에 나온대로 각 자릿수를 변수에 담아 처리했으면 속도가 더 빨랐을 것 같다. 다음엔 계산식으로 생각해 낼 수 있도록 가급적 문자열 사용을 줄여봐야겠당